Common problems and usage
Dynamic programming is similar to the divide-and-conquer method, solving problems by combining the solutions to subproblems. But the main difference is that dynamic programming doesn’t solve the common subproblem repeatedly. A DP algorithm solves subproblems just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subproblem.
How to develop a DP algorithm
- Characterize the structure of an optimal solution.
- Recursively define the value of an optimal solution.
- Compute the value of an optimal solution, typically in a bottom-up fashion.
- Construct an optimal solution from computed information.
Memoization and Tabulation
If we observe that a recursive solution is inefficient because it solves the same subproblems repeatedly, we arrange for each subproblem to be solved only once, saving its solution.
- DP uses additional memory to save computation time - a time-memory trade-off.
Top-down or Memoization
- Use a recursive approach similar to the non-DP solution.
- Add a memoization table (array or hash map) to store the results of subproblems.
- Before computing a subproblem, check if it's already solved in the memo table.
Bottom-up or Tabulation
- Create a table to store the maximum profit for each rod length from 1 to n.
- Fill the table iteratively, using smaller subproblems to solve larger ones.
- The final answer will be in the last cell of the table.
Example - Matrix Multiplication