Dynamic programming problems scare me A LOT.
Yeah, it could be quite frustrating, if you haven’t found the key assertions.
Dynamic Programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again.
The main idea behind DP is to save duplicated caculations.
Trade space for time.
Basic Abstractions
Name | Summary |
---|---|
Typical dynamicprogramming problems | #knapsack, #intervaldp, #treedp, #bitmaskdp |
Typical dynamicprogramming problems | #divideconquer, #lis, #lcs, #minimax, #coin |
Typical dynamicprogramming problems | #paintfence, #frogjump, #houserobber |
Optimal Substructure | |
DP vs recursive+memoization |
Top Questions
Name | Example |
---|---|
DP needs only O(1) space | LintCode: Computer Maintenance |
Some initialization can be skipped | LeetCode: Longest Arithmetic Subsequence of Given Difference |
Some initialization can be skipped | LeetCode: Bomb Enemy |
Instead of left-to-right, do it from right-to-left | Maximum Length of Repeated Subarray, LeetCode: Largest Sum of Averages |
Ugly Number II | LeetCode: Ugly Number II |
DP based on values instead of positions | LeetCode: Minimum Distance to Type a Word Using Two Fingers |
Key Parts In DP Problems:
- Key observation is crucial. Watch careful for how the states transit?
- Walk through with smaller cases manually. And detect the pattern.
Different Types Of DP Functions:
- Interesting dp funcitons
Domino and Tromino Tiling
dp(i) = dp(i-1)+dp(i-2)+2*(dp(i-3)+dp(i-4)+…+dp(0)) - DP saves intermediate results, not the final ones
Champagne Tower - dp(i) = min(dp(i), dp[i-coin[j]]+1)
Coin Change - Function: f(i, j): Longest Palindromic Subsequence
- Coin Change 2
- Save the base case: Maximum Length of Repeated Subarray
The most impressive problems to me:
See all dynamicprogramming problems: #dynamicprogramming
- Review: Dynamic Programming Problems
- LintCode: Minimum Cycle Section
- Lintcode: Digital Flip
- LintCode: Computer Maintenance
- LeetCode: Zuma Game
- LeetCode: Word Break
- LeetCode: Wildcard Matching
- LeetCode: Video Stitching
- LeetCode: Valid Palindrome III
- LeetCode: Unique Substrings in Wraparound String
- LeetCode: Unique Paths II
- LeetCode: Unique Paths
- LeetCode: Unique Binary Search Trees II
- LeetCode: Unique Binary Search Trees
- LeetCode: Uncrossed Lines
- LeetCode: Ugly Number II
- LeetCode: Triangle
- LeetCode: Toss Strange Coins
- LeetCode: Text Justification
- LeetCode: Target Sum
- LeetCode: Tallest Billboard
- LeetCode: Student Attendance Record II
- LeetCode: Strange Printer
- LeetCode: Stone Game II
- LeetCode: Stone Game
- LeetCode: Split Array Largest Sum
- LeetCode: Smallest Sufficient Team
- LeetCode: Shortest Path with Alternating Colors
- LeetCode: Shortest Common Supersequence
- LeetCode: Shopping Offers
See more blog posts.