Review: Dynamic Programming Problems Posted on January 22, 2018October 6, 2019 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 optimal substructure DP vs recursive+memoization Scenarios Code Skeleton 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 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 See all dynamicprogramming problems: #dynamicprogramming Review: Dynamic Programming ProblemsLintCode: Minimum Cycle SectionLintCode: Frog JumpLintcode: Digital FlipLintCode: Computer MaintenanceLintCode: Card GameLeetcode: Word BreakLeetcode: Video StitchingLeetcode: Valid Palindrome IIILeetcode: Unique Paths IILeetcode: Unique PathsLeetcode: Unique Binary Search Trees IILeetcode: Unique Binary Search TreesLeetcode: TriangleLeetcode: Toss Strange CoinsLeetcode: Tallest BillboardLeetcode: Student Attendance Record IILeetcode: Shortest Path with Alternating ColorsLeetcode: Shortest Common SupersequenceLeetcode: Remove BoxesLeetcode: Regular Expression MatchingLeetcode: Race CarLeetcode: Partition Equal Subset SumLeetcode: Paint HouseLeetcode: Paint FenceLeetcode: Out of Boundary PathsLeetcode: Ones and ZeroesLeetcode: One Edit DistanceLeetcode: New 21 GameLeetcode: Minimum Swaps To Make Sequences IncreasingLeetcode: Minimum Path SumLeetcode: Minimum Falling Path SumLeetcode: Minimum Cost Tree From Leaf ValuesLeetcode: Minimum Cost For TicketsLeetcode: Minimum ASCII Delete Sum for Two StringsLeetcode: Min Cost Climbing StairsLeetcode: Maximum Sum of Two Non-Overlapping SubarraysLeetcode: Maximum Length of Repeated SubarrayLeetcode: Maximum Length of Pair ChainLeetcode: Maximal SquareLeetcode: 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: Interleaving StringLeetcode: Integer BreakLeetcode: House Robber IILeetcode: House RobberLeetcode: Gray CodeLeetcode: Flip String to Monotone IncreasingLeetcode: Find the Derangement of An ArrayLeetcode: 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 PrimesLeetcode: Combination Sum IVLeetcode: Climbing StairsLeetcode: Champagne TowerLeetcode: Can I WinLeetcode: Bomb EnemyLeetcode: Bitwise ORs of SubarraysLeetcode: Best Time to Buy and Sell Stock with Transaction FeeLeetcode: Beautiful ArrayLeetcode: 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