Dynamic Programming
Turn exponential recursions into polynomial algorithms by remembering subproblems.
7 articles~45 min total
0/7
Introduction
Classic problems
- Knapsack Problem0-1, complete and bounded knapsack in one array, with the loop directions that make each version work, and a big-integer bitset trick for subset sum.6 minIntermediate
- Longest Increasing SubsequenceFind the longest strictly increasing subsequence in O(n²) with DP and in O(n log n) with binary search, and restore the subsequence itself.7 minIntermediate
Optimizations
- Divide and Conquer DPSpeed up a DP of the form dp[i][j] = min over k of dp[i-1][k] + C(k, j) from O(m n²) to O(m n log n) when the optimal split point is monotone.6 minAdvanced
- Knuth's OptimizationSpeed up range DPs of the form dp[i][j] = min over k of dp[i][k] + dp[k][j] + C(i, j) from O(n³) to O(n²) by restricting the split point.7 minAdvanced
Tasks
- DP on a Broken Profile: Domino TilingsCount the ways to tile a grid with dominoes by processing cell by cell and remembering a bitmask of the frontier, the broken profile.6 minAdvanced
- Finding the Largest Zero SubmatrixFind the largest rectangle of zeros in a binary matrix in O(nm) using column heights and a monotonic stack.5 minIntermediate