AlgoViz
HomeDynamic Programming

Dynamic Programming

Overlapping subproblems — solve each once, reuse forever.

0/ 65 understood · 0%
Walkthroughs
41
Problems
65
Start here
65 shown
  1. FundamentalsOverlapping subproblems · a table you fill onceEasy
  2. Solving a Question with DPState → recurrence → base case → order → answerEasy
  3. Climbing Stairsways(i) = ways(i−1) + ways(i−2) · FibonacciEasy
  4. Maximum Subarraycur = max(nums[i], cur + nums[i]) · Kadane'sMedium
  5. House Robberdp[i] = max(dp[i−1], dp[i−2] + nums[i])Medium
  6. Coin Changedp[a] = 1 + min(dp[a − coin]) · fewest coinsMedium
  7. Longest Common SubsequenceGrid DP · match → diagonal+1, else max(up, left)Medium
  8. Unique PathsGrid DP · dp[i][j] = dp[i−1][j] + dp[i][j−1]Medium
  9. Longest Increasing SubsequencePatience sorting · O(n log n)Medium
  10. Word Breakdp[i] = can s[0..i) split into dictionary wordsMedium
  11. Practice problems
  12. Frog JumpBest of stepping one or twoMedium
  13. Frog jump with K distancesBest over the previous k stepsMedium
  14. Maximum sum of non adjacent elementsTake it and skip one, or skip itMedium
  15. Ninja's trainingState includes yesterday's activityMedium
  16. Grid Unique Paths : DP on GridsPaths in = paths from above + paths from the leftMedium
  17. Unique paths IIAn obstacle contributes zero pathsMedium
  18. Minimum Falling Path SumBest of three cells aboveMedium
  19. TriangleFill upward from the baseMedium
  20. Ninja and his FriendsTwo positions, one shared rowMedium
  21. Subset sum equal to targetTake or skip, indexed by remaining targetHard
  22. Partition equal subset sumSubset sum for half the totalHard
  23. Partition a set into two subsets with minimum absolute sum differenceFind every reachable subset sumHard
  24. Count subsets with sum KAdd the two branches instead of OR-ing themHard
  25. Count partitions with given differenceSolve for one subset's sumHard
  26. Assign CookiesSort both, match greedilyEasy
  27. Minimum CoinsUnbounded: stay on the same coinHard
  28. Target sumSigns become a subset choiceHard
  29. Coin Change 2Coins in the outer loop, or you count ordersHard
  30. Unbounded knapsackTaking an item does not consume itHard
  31. Rod Cutting ProblemUnbounded knapsack in disguiseHard
  32. Print Longest Common SubsequenceWalk the table backwardsHard
  33. Longest common substringReset to zero on a mismatchHard
  34. Longest palindromic subsequenceLCS of the string with its reverseHard
  35. Minimum insertions to make string palindromeKeep the longest palindromic coreHard
  36. Minimum insertions or deletions to convert string A to BEverything outside the LCS must changeHard
  37. Shortest common supersequenceBoth strings, sharing the LCS onceHard
  38. Distinct subsequencesMatch or skip the character of sHard
  39. Edit distanceInsert, delete or replace — take the cheapestHard
  40. Wildcard matching'*' either consumes a character or nothingHard
  41. Best time to buy and sell stockCheapest so far, best profit so farMedium
  42. Best time to buy and sell stock IICollect every upward moveMedium
  43. Best time to buy and sell stock IIIFour states across the dayMedium
  44. Best time to buy and sell stock IVThe four-state machine, generalised to kMedium
  45. Best Time to Buy and Sell Stock with CooldownThree states: holding, sold, freeMedium
  46. Best time to buy and sell stock with transaction feesCharge the fee once per transactionMedium
  47. Print Longest Increasing SubsequenceStore a predecessor with each lengthMedium
  48. Largest Divisible SubsetSort, then LIS with a divisibility testMedium
  49. Longest String ChainSort by length, extend by one characterMedium
  50. Longest Bitonic SubsequenceLIS from the left, LIS from the rightMedium
  51. Number of Longest Increasing SubsequencesCarry a count alongside each lengthMedium
  52. Matrix chain multiplicationTry every split pointHard
  53. Minimum cost to cut the stickInterval DP over the cut positionsHard
  54. Burst balloonsChoose the balloon burst lastHard
  55. Different Ways to Evaluate a Boolean ExpressionCount true and false ways separatelyMedium
  56. Palindrome partitioning IICut where the prefix is a palindromeHard
  57. Partition Array for Maximum SumTry every group length ending hereMedium
  58. Maximum Rectangle Area with all 1's|A histogram per rowHard
  59. Count Square Submatrices with All Ones|Each cell counts the squares ending thereEasy
  60. Solving a Question with Dynamic ProgrammingState, recurrence, base case, orderMedium
  61. Counting BitsReuse the answer for half the numberMedium
  62. Decode WaysOne digit or two, if validMedium
  63. Maximal SquareThe same recurrence, take the maximumMedium
  64. Maximum Profit in Job SchedulingSort by end, binary search the last compatible jobMedium
  65. Paint HouseBest cost per colour, per houseMedium
  66. Paint House IITrack the best two previous coloursMedium