Review: Dynamic Programming Problems Posted on January 22, 2018July 26, 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, #bitmaskdp Typical dynamicprogramming problems #divideconquer, #lis, #lcs, #minimax, #coin Typical dynamicprogramming problems #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 28 dp + greedy O(n) Leetcode: House Robber 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 MaintenanceLeetCode: Zuma GameLeetCode: Word BreakLeetCode: Wildcard MatchingLeetCode: Video StitchingLeetCode: Valid Palindrome IIILeetCode: Unique Substrings in Wraparound StringLeetCode: Unique Paths IILeetCode: Unique PathsLeetCode: Unique Binary Search Trees IILeetCode: Unique Binary Search TreesLeetCode: Uncrossed LinesLeetCode: Ugly Number IILeetCode: TriangleLeetCode: Toss Strange CoinsLeetCode: Text JustificationLeetCode: Target SumLeetCode: Tallest BillboardLeetCode: Student Attendance Record IILeetCode: Strange PrinterLeetCode: Stone Game IILeetCode: Stone GameLeetCode: Split Array Largest SumLeetCode: Smallest Sufficient TeamLeetCode: Shortest Path with Alternating ColorsLeetCode: Shortest Common SupersequenceLeetCode: Shopping OffersLeetCode: Restore The ArrayLeetCode: Remove BoxesLeetCode: Regular Expression MatchingLeetCode: Race CarLeetCode: Partition to K Equal Sum SubsetsLeetCode: Partition Equal Subset SumLeetCode: Palindrome RemovalLeetCode: Palindrome Partitioning IIILeetCode: Palindrome Partitioning IILeetCode: Paint House IIILeetCode: Paint HouseLeetCode: Paint FenceLeetCode: Out of Boundary PathsLeetCode: Ones and ZeroesLeetCode: One Edit DistanceLeetCode: Numbers With Same Consecutive DifferencesLeetCode: Number of Ways to Wear Different Hats to Each OtherLeetCode: Number of Ways to Stay in the Same Place After Some StepsLeetCode: Number of Ways to Paint N x 3 GridLeetCode: Number of Ways of Cutting a PizzaLeetCode: New 21 GameLeetCode: Minimum Swaps To Make Sequences IncreasingLeetCode: Minimum Score Triangulation of PolygonLeetCode: Minimum Path SumLeetCode: Minimum Number of Taps to Open to Water a GardenLeetCode: Minimum Falling Path Sum IILeetCode: Minimum Falling Path SumLeetCode: Minimum Distance to Type a Word Using Two FingersLeetCode: Minimum Difficulty of a Job ScheduleLeetCode: Minimum Cost Tree From Leaf ValuesLeetCode: Minimum Cost to Merge StonesLeetCode: Minimum Cost For TicketsLeetCode: Minimum ASCII Delete Sum for Two StringsLeetCode: Min Cost Climbing StairsLeetCode: Maximum Vacation DaysLeetCode: Maximum Students Taking ExamLeetCode: Maximum Profit in Job SchedulingLeetCode: Maximum Length of Repeated SubarrayLeetCode: Maximum Length of Pair ChainLeetCode: Maximal SquareLeetCode: Make Array Strictly IncreasingLeetCode: Longest Turbulent SubarrayLeetCode: Longest String ChainLeetCode: Longest Palindromic SubsequenceProtected: LeetCode: Longest Line of Consecutive One in MatrixLeetCode: Longest Increasing SubsequenceLeetCode: Longest Common SubsequenceLeetCode: Longest Arithmetic Subsequence of Given DifferenceLeetCode: Length of Longest Fibonacci SubsequenceLeetCode: Last Stone Weight IILeetCode: Largest Sum of AveragesLeetCode: Largest Divisible SubsetLeetCode: Knight DialerLeetCode: Jump Game VLeetCode: Interleaving StringLeetCode: Integer BreakLeetCode: House Robber IILeetCode: House RobberLeetCode: Grumpy Bookstore OwnerLeetCode: Gray CodeLeetCode: Frog JumpLeetCode: Flip String to Monotone IncreasingLeetCode: Find the Derangement of An ArrayLeetCode: Find All Good StringsLeetCode: Filling Bookcase ShelvesLeetCode: Fibonacci NumberLeetCode: Edit DistanceLeetCode: Dungeon GameLeetCode: Domino and Tromino TilingLeetCode: Divisor GameLeetCode: Distinct Subsequences IILeetCode: Delete Operation for Two StringsLeetCode: Counting BitsLeetCode: Count Vowels PermutationLeetCode: Count Triplets That Can Form Two Arrays of Equal XORLeetCode: Count Square Submatrices with All OnesLeetCode: Count PrimesLeetCode: Count Number of TeamsLeetCode: Count All Valid Pickup and Delivery OptionsLeetCode: Constrained Subset SumLeetCode: Constrained Subsequence SumLeetCode: Combination Sum IVLeetCode: Coin PathLeetCode: Climbing StairsLeetCode: Champagne TowerLeetCode: Can I WinLeetCode: Burst BalloonsLeetCode: Build Array Where You Can Find The Maximum Exactly K ComparisonsLeetCode: Bomb EnemyLeetCode: Bitwise ORs of SubarraysLeetCode: Binary Trees With FactorsLeetCode: Binary Tree CamerasLeetCode: Best Time to Buy and Sell Stock with Transaction FeeLeetCode: Best Time to Buy and Sell Stock with CooldownLeetCode: Arithmetic Slices II – SubsequenceLeetCode: All Possible Full Binary TreesLeetCode: Airplane Seat Assignment ProbabilityLeetCode: 4 Keys KeyboardLeetCode: 2 Keys Keyboard See more blog posts. Post Views: 10