Dynamic Programming
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.
Steps
- Recursion
- 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
Concepts
Simple. most of the Dynamic Programming problems are solved in two ways:
- Tabulation: Bottom Up
- Memoization: Top Down
More advanced concepts are explored for Competitive Programming https://codeforces.com/blog/entry/8219
- 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
Applications
- Reinforcement Learning
- Grid problems
- Coin Problem
- Knapsack DP
Other:
Other
Recursive vs. Iterative DP
- Errichto says this iterative, bottom-up approach, is preferred in Competitive Programming
- The Competitive Programmer’s Handbook also says the same, because it is shorter and has lower constant factors.
- However, its often easier to think about DP solutions in terms of Recursive Algorithms