Dynamic programming is a technique that combines the correctness of complete search and the efficiency of greedy algorithms.
Dynamic Programming is “Smart Brute-Forcing”.
There are two uses for dynamic programming:
- Finding an optimal solution: We want to find a solution that is as large as possible or as small as possible.
- Counting the number of solutions: We want to calculate the total number of possible solutions.
Dynamic programming can be applied if the problem can be divided into overlapping subproblems that can be solved independently.
- Define Subproblems count # subproblems
- Guess (part of solution) count # choices
- Relate Subproblem Solutions compute time/subproblem
- Apply Memoization (top-down DP), or
- Apply Tabulation (Iterative / Bottom-Up DP)
- Make sure to check Topological Order
Simple. most of the Dynamic Programming problems are solved in two ways:
- Top-Down DP
- Bottom-Up DP
- Divide and Conquer DP
- Convex Hull DP
- Knuth’s Optimization DP
- Bitmask DP
- Knapsack DP
- Range DP
DP on trees: https://codeforces.com/blog/entry/20935