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

1. Recursion
   1. Define Subproblems $\to$ count # subproblems
   2. Guess (part of solution) $\to$ count # choices
   3. Relate Subproblem Solutions $\to$ compute time/subproblem
2. Apply Memoization (top-down DP), or
3. Apply Tabulation (Iterative / Bottom-Up DP)
4. Make sure to check Topological Order

Concepts §

Simple. most of the Dynamic Programming problems are solved in two ways:  

1. Tabulation: Bottom Up
2. 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:

• Backtracking

Other §

Recursive vs. Iterative DP §

1. Errichto says this iterative, bottom-up approach, is preferred in Competitive Programming
2. The Competitive Programmer’s Handbook also says the same, because it is shorter and has lower constant factors.
3. However, its often easier to think about DP solutions in terms of Recursive Algorithms