Dynamic Programming

Dynamic programming solves a problem by combining answers to overlapping subproblems, each computed once and stored. Reach for it when a problem asks for an optimum (max, min, or count) and the choice at each step depends on the results of smaller versions of the same problem.

55 LeetCode problems solved with the Dynamic Programming pattern. Practice them with spaced repetition so the pattern sticks.

• Best Time to Buy and Sell StockEASY · O(n)
• Best Time to Buy and Sell Stock IIIHARD · O(n)
• Best Time to Buy and Sell Stock IVHARD · O(n*k)
• Best Time to Buy and Sell Stock with CooldownMEDIUM · O(n)
• Best Time to Buy and Sell Stock with Transaction FeeMEDIUM · O(n)
• Burst BalloonsHARD · O(n^3)
• Climbing StairsEASY · O(n)
• Coin ChangeMEDIUM · O(amount * n)
• Coin Change IIMEDIUM · O(n * amount)
• Combination Sum IVMEDIUM · O(target * n)
• Counting BitsEASY · O(n)
• Decode WaysMEDIUM · O(n)
• Delete Operation for Two StringsMEDIUM · O(m*n)
• Distinct SubsequencesHARD · O(m * n)
• Domino and Tromino TilingMEDIUM · O(n)
• Edit DistanceHARD · O(m*n)
• Extra Characters in a StringMEDIUM · O(n^2)
• Fibonacci NumberEASY · O(n)
• House RobberMEDIUM · O(n)
• House Robber IIMEDIUM · O(n)
• Integer BreakMEDIUM · O(n)
• Interleaving StringMEDIUM · O(m * n)
• Jump Game VIIMEDIUM · O(n)
• Last Stone Weight IIMEDIUM · O(n * S)
• Longest Common SubsequenceMEDIUM · O(m*n)
• Longest Increasing Path in a MatrixHARD · O(m*n)
• Longest Increasing SubsequenceMEDIUM · O(n^2)
• Longest Palindromic SubsequenceMEDIUM · O(n^2)
• Longest Palindromic SubstringMEDIUM · O(n^2)
• Longest Turbulent SubarrayMEDIUM · O(n)
• Maximal SquareMEDIUM · O(m * n)
• Maximum Length of Repeated SubarrayMEDIUM · O(n*m)
• Maximum Product SubarrayMEDIUM · O(n)
• Maximum Profit in Job SchedulingHARD · O(n log n)
• Maximum SubarrayMEDIUM · O(n)
• Maximum Sum Circular SubarrayMEDIUM · O(n)
• Min Cost Climbing StairsEASY · O(n)
• Minimum Path SumMEDIUM · O(m * n)
• N-th Tribonacci NumberEASY · O(n)
• Ones and ZeroesMEDIUM · O(L * m * n)
• Palindromic SubstringsMEDIUM · O(n^2)
• Partition Equal Subset SumMEDIUM · O(n * target)
• Pascal's TriangleEASY · O(n^2)
• Perfect SquaresMEDIUM · O(n * sqrt(n))
• Regular Expression MatchingHARD · O(m * n)
• Stone GameMEDIUM · O(n^2)
• Stone Game IIMEDIUM · O(n^3)
• Stone Game IIIHARD · O(n)
• Target SumMEDIUM · O(n * P)
• TriangleMEDIUM · O(n^2)
• Uncrossed LinesMEDIUM · O(m*n)
• Unique Binary Search TreesMEDIUM · O(n^2)
• Unique PathsMEDIUM · O(m*n)
• Unique Paths IIMEDIUM · O(m*n)
• Word BreakMEDIUM · O(n^2)