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.

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

1. Tabulation: Bottom Up
2. Memoization: Top Down

• I think I’ve gotten relatively good at DP thanks to CS341, forced me to think about formulating the subproblems fast

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

• Coin Problem
• Interval Scheduling
• Knapsack DP
• Longest Increasing Subsequence
• Longest Common Subsequence
• Longest Palindromic Sequence
• Optimal BST

Other:

• Reinforcement Learning
• Grid problems
• 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

Older Notes

These were taken from the freecodecamp DP video.

Steps (more application to top-down DP)

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

Dynamic programming vs. Divide-and-Conquer?

• dynamic programming usually deals with all input sizes $1,\dots ,n$
• DAC may not solve “subproblems”
• DAC algorithms not easy to rewrite iteratively

Concepts