Review: Dynamic Programming Problems Posted on January 22, 2018February 9, 2020 by braindenny 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, #minimax, #divideconquer Typical dynamicprogramming problems #lis, #lcs, #coin, #paintfence, #frogjump, #houserobber Optimal Substructure DP vs recursive+memoization Top Questions Num Problem Time Complexity Summary 1 Maximum subarray problem – Kadane’s algorithm O(n) LeetCode: Maximum Subarray 2 LIS – Longest increasing subsequence O(n) LeetCode: Longest Increasing Subsequence 3 LCS – Longest Common Subsequence O(n*m) LeetCode: Longest Common Subsequence 4 LPS – Longest Palindromic Subsequence O(n) LeetCode: Longest Palindromic Subsequence 5 Longest Palindromic Substring O(n2) LeetCode: Longest Palindromic Substring 6 Edit distance of two strings O(n2) LeetCode: Edit Distance 7 Maximal Square O(n*m) Leetcode: Maximal Square 8 Maximum profits with certain costs O(n2) LeetCode: 4 Keys Keyboard 9 Count of distinct subsequence O(n) LeetCode: Distinct Subsequences II 10 Count out of boundary paths in a 2D matrix O(n*m*N) LeetCode: Out of Boundary Paths 11 Regular Expression Matching O(n*m) LeetCode: Regular Expression Matching 12 Wildcard Matching O(n*m) LeetCode: Wildcard Matching 13 Multiple choices for each step O(n*m) LeetCode: Filling Bookcase Shelves 14 Knapsack: put array to bag A, B or discard it O(n*s) LeetCode: Tallest Billboard 15 Knapsack problem to maximize benefits O(n*s) LeetCode: Coin Change 16 Minimum Cost to Merge Stones O(n3) LeetCode: Minimum Cost to Merge Stones 17 DP over interval: Minimum-weight triangulation O(n3) LeetCode: Minimum Score Triangulation of Polygon 18 Burst Balloons O(n3) LeetCode: Burst Balloons 19 DP based on states, instead of possible actions O(n) LeetCode: Best Time to Buy and Sell Stock with Cooldown 20 Remove Boxes O(n4) LeetCode: Remove Boxes 21 Largest Sum of Averages O(k*n*n) LeetCode: Largest Sum of Averages 22 Uncrossed Lines O(n*m) LeetCode: Uncrossed Lines 23 treedp: Binary Trees With Factors O(n2) LeetCode: Binary Trees With Factors 24 DP based on values instead of positions O(n) LeetCode: Minimum Distance to Type a Word Using Two Fingers 25 Video Stitching O(n*m) LeetCode: Video Stitching 26 Maximum Profit in Job Scheduling O(n*log(n)) Leetcode: Maximum Profit in Job Scheduling 27 Machine state O(n) Leetcode: Student Attendance Record II 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: Min Cost Climbing Stairs Maximum Length of Repeated Subarray CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups See all dynamicprogramming problems: #dynamicprogramming Review: Dynamic Programming ProblemsLintCode: Minimum Cycle SectionLintcode: Digital FlipLintCode: Computer MaintenanceLintCode: Card GameLeetcode: Zuma GameLeetcode: Word BreakLeetCode: Wildcard MatchingLeetCode: Video StitchingLeetcode: Valid Palindrome III See more blog posts. Post Views: 10