# 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