D&C/Greedy/Dynamic

The Divide and Conquer Approach

1. Divide the problem into Subproblems that are smaller instances of the same problem.
2. Conquer the subproblem by solving them recursively. Use “base case” for the simplest subproblem. (Recursion is bottom up)
3. Combine the solutions to the subproblems into the solution for the original problem.

Divide and Conquer usually generates brand-new problem at each step of recursion.

Elements of Dynamic Programming

For any optimization Problem, to be considered for the Dynamic Programming Problem, TWO key elements are needed.

1. Optimal substructure : Problem exhibits optimal substructure, and optimal solution is built from optimal solutions to subproblem.
2. Overlapping subproblems : space of subproblems must be small. The total number of distinct subproblems is polynomial in the input size.

Dynamic programming algorithm typically take advantage of overlapping subproblem by solving each subproblem once and then storing the solution in a table where it can be looked up when needed.

A bottom-up dynamic-programming algorithm usually outperforms the corresponding top-down memoized algorithm by a constant factor, because the bottom-up algorithm has no overhead for recursion and less overhead for maintaining the table.

Elements of Greedy Strategy

A greedy algorithm makes choice that seems best at the moment.

This heuristic strategy does not always produce an optimal solution but sometimes it does.

1. Determine the optimal substructure of the problem.
2. Develop a recursive solution.
3. Show that if we make the greedy choice, then only one subproblem remains.
4. Prove that it is always safe to make the greedy choice. (Steps 3 and 4 can occur in either order.)
5. Develop a recursive algorithm that implements the greedy strategy.
6. Convert the recursive algorithm to an iterative algorithm.