Skip to content
dsa450for five year olds

Topic 15 of 15

Dynamic Programming

Writing answers on a chart so you never redo homework.

Dynamic programming is not doing the same homework twice. If a big problem is made of smaller problems that repeat, solve each small one once and write its answer in a chart. Then build bigger answers from the chart. The hard part is choosing what each box in the chart means.

What you will be able to do

Spotting repeated subproblemsDefining the state1D tables: climbing, robbing, jumps2D tables: knapsack, LCS, edit distanceInterval and tree DP
0/60
60 problems

Meet dynamic programming

01 / 04

tree
f4f3f2f1f0f1f2f1f0

Fibonacci by plain asking: fib(4) asks fib(3) and fib(2). fib(2) gets asked twice. That is wasted work.

  • looking now
  • checking
  • done
  • answer
  • rejected
  • just added

The problems

In order from easier to harder ideas. The ones marked must do come up in interviews again and again.

  1. 01Coin Change ProblemCount the different handfuls of coins that pay an exact amount, when you have as many coins of each kind as you like.Unbounded knapsack
  2. 02Knapsack ProblemPack a bag that can only carry so much weight with the set of toys that gives the most fun, taking each toy whole or not at all.2D dynamic programming
  3. 03Binomial Coefficient ProblemCount how many different groups of k friends you can pick from n friends, using a pyramid where every number is the sum of the two above it.2D dynamic programming
  4. 04Permutation Coefficient ProblemCount the ways to hand out k different prizes to n kids, one prize per kid, where who gets which prize matters.1D dynamic programming
  5. 05Program for nth Catalan NumberCount how many different tree shapes you can build from n nodes, the famous number that also counts valid bracket strings and many other things.1D dynamic programming
  6. 06Matrix Chain MultiplicationChoose where to put the brackets when multiplying a chain of matrices so the total number of small multiplications is as low as possible.Interval dynamic programming
  7. 07Edit DistanceFind the fewest single-letter changes (add, remove or swap a letter) that turn one word into another.2D dynamic programming
  8. 08Subset Sum ProblemDecide whether you can pick some of the numbers so they add up to exactly a target.2D dynamic programming
  9. 09Friends Pairing ProblemCount the ways a group of friends can go to a dance, where each friend goes alone or with exactly one partner.1D dynamic programming
  10. 10Gold Mine ProblemWalk through a grid of gold from the left edge to the right edge, stepping up-right, right or down-right, and collect as much gold as you can.2D dynamic programming
  11. 11Assembly Line Scheduling ProblemWalk a car through two lines of work stations, hopping between lines when it saves time, and find the fastest way out.1D dynamic programming
  12. 12Painting the Fence problemCount the ways to paint a row of fence posts with k colors so that no three posts in a row share a color.1D dynamic programming
  13. 13Maximize The Cut SegmentsCut a ribbon into as many pieces as you can, when every piece must be one of three allowed sizes and nothing may be left over.1D dynamic programming
  14. 14Longest Common SubsequenceFind the longest list of letters that shows up in both words in the same order, even if other letters sit in between.2D dynamic programming
  15. 15Longest Repeated SubsequenceFind the longest pattern of letters that you can pick out of one word twice, in order, without ever pairing a letter with itself.2D dynamic programming
  16. 16Longest Increasing SubsequencePick numbers from left to right, skipping any you like, to make the longest chain where every number is bigger than the one before.Binary search on tails
  17. 17Space Optimized Solution of LCSFind the length of the longest common subsequence of two words while keeping only two short rows of the table instead of the whole table.2D dynamic programming
  18. 18LCS (Longest Common Subsequence) of three stringsFind the longest list of letters that appears, in order, inside all three words at once.3D dynamic programming
  19. 19Maximum Sum Increasing SubsequencePick numbers that keep getting bigger from left to right so that their total is as large as possible.1D dynamic programming
  20. 20Count all subsequences having product less than KCount the groups of numbers you can pick from a list, keeping their order, whose product stays below k.1D dynamic programming
  21. 21Longest subsequence such that difference between adjacent is onePick numbers in order so that each picked number is exactly one more or one less than the one before, and make the chain as long as you can.Hash map dynamic programming
  22. 22Maximum subsequence sum such that no three are consecutiveGrab the most cookies from a row of jars without ever taking from three jars in a row.1D dynamic programming
  23. 23Egg Dropping ProblemWith a few eggs and a tall building, find the fewest drops that always tell you the highest floor an egg survives.2D dynamic programming
  24. 24Maximum Length Chain of PairsLine up as many number pairs as you can, where each next pair must start after the previous one ends.Greedy by sorting
  25. 25Maximum size square sub-matrix with all 1sFind the biggest square of 1s in a grid by letting every cell ask its three neighbors how big a square ends there.2D dynamic programming
  26. 26Maximum sum of pairs with specific differenceMake partner pairs of close numbers so the paired numbers add up to the biggest total, with nobody in two pairs.1D dynamic programming
  27. 27Min Cost Path ProblemCross a grid of toll squares from the top left to the bottom right paying as few coins as possible.2D dynamic programming
  28. 28Maximum difference of zeros and ones in binary stringFind the stretch of a 0 and 1 string where the 0s beat the 1s by the most, by turning it into a points game.Kadane running sum
  29. 29Minimum number of jumps to reach endHop from the first square to the last in as few jumps as possible, when each square tells you how far you may jump.Greedy jump windows
  30. 30Minimum cost to fill given weight in a bagFill a bag to an exact weight with packets you can buy as often as you like, spending as little as possible.Unbounded knapsack
  31. 31Minimum removals from array to make max min less than or equal to KSend the fewest kids home so that the tallest and the shortest kid left differ by at most K.Sliding window
  32. 32Longest Common SubstringFind the longest piece of letters, with no gaps, that appears in both words.2D dynamic programming
  33. 33Count number of ways to reach a given score in a gameCount the different mixes of 3, 5 and 10 point moves that add up to an exact score, where the order of moves does not matter.Unbounded knapsack
  34. 34Count Balanced Binary Trees of Height hCount the different shapes of tree with exactly h rows where, at every node, the left and right sides are almost the same height.1D dynamic programming
  35. 35Largest Sum Contiguous SubarrayFind the stretch of numbers next to each other that adds up to the biggest total.1D dynamic programmingMust do
  36. 36Smallest sum contiguous subarrayFind the run of days in a row where your sticker count dropped the most, which is the stretch of an array with the smallest sum.Kadane's algorithm
  37. 37Unbounded Knapsack (Repetition of items allowed)Fill a bag of fixed size with the most valuable mix of items when every item can be taken as many times as you like.1D dynamic programming
  38. 38Word Break ProblemDecide if a string with no spaces can be cut into pieces that are all words from a given dictionary.1D dynamic programming
  39. 39Largest Independent Set ProblemInvite as many people from a family tree as you can, but never invite a parent together with their own child.Tree dynamic programming
  40. 40Partition problemDecide if a pile of numbers can be split into two groups with exactly the same total.2D dynamic programming
  41. 41Longest Palindromic SubsequenceCross out as few letters as you can so the letters left read the same forwards and backwards, and say how many are left.Interval dynamic programming
  42. 42Count All Palindromic Subsequence in a given StringCount every way to keep some letters of a word, in order, so that what is left reads the same forwards and backwards.Interval dynamic programming
  43. 43Longest Palindromic SubstringFind the longest unbroken piece of a word that reads the same forwards and backwards.Expand around center
  44. 44Longest alternating subsequencePick numbers in order so they go up, down, up, down like a zigzag, and make the zigzag as long as you can.1D dynamic programming
  45. 45Weighted Job SchedulingPick jobs that do not overlap in time so that the money you earn is as large as possible.1D dynamic programming
  46. 46Coin game winner where every player has three choicesTwo friends take 1, x or y coins in turns from a pile, and whoever takes the last coin wins: decide who wins if both play perfectly.Game DP with win and lose states
  47. 47Count Derangements (Permutation such that no element appears in its original position)Count the ways to hand back the hats at a party so that nobody gets their own hat.1D dynamic programmingMust do
  48. 48Maximum profit by buying and selling a share at most twiceMake the most money from at most two buy and sell trips by carrying four running money totals through the days.State machine DPMust do
  49. 49Optimal Strategy for a GameTwo smart players take turns grabbing a coin from either end of a row, and you work out the most money the first player can be sure to get.Interval dynamic programming
  50. 50Optimal Binary Search TreeArrange sorted keys into a search tree so that the keys people ask for most often sit near the top and the total number of search steps is as small as possible.Interval dynamic programming
  51. 51Palindrome Partitioning ProblemCut a word into the fewest pieces so that every piece reads the same forwards and backwards.1D dynamic programming
  52. 52Word Wrap ProblemBreak a list of words into lines of a fixed width so the empty space at the ends of the lines looks as even as possible.1D dynamic programming
  53. 53Mobile Numeric Keypad ProblemCount how many numbers of length n you can type on an old phone keypad if every press stays on the same key or moves to a key that touches it.2D dynamic programmingMust do
  54. 54Boolean Parenthesization ProblemCount the ways to put brackets on a chain of true and false cards so the whole thing comes out true.Interval dynamic programming
  55. 55Largest rectangular sub-matrix whose sum is 0Find the biggest rectangle inside a grid of numbers whose numbers add up to exactly zero.Prefix sums with a hash map
  56. 56Largest area rectangular sub-matrix with equal number of 1s and 0sIn a grid of 0s and 1s, find the biggest rectangle that has exactly as many 0s as 1s.Prefix sums with a hash mapMust do
  57. 57Maximum sum rectangle in a 2D matrixFind the rectangle of numbers in a grid with the biggest total by squashing column strips into one line and running the best stretch trick.Kadane on column strips
  58. 58Maximum profit by buying and selling a share at most k timesKnowing all future prices, make the most money with at most k buy and sell trips, holding one share at a time.2D dynamic programming
  59. 59Find if a string is interleaved of two other stringsCheck if a long word can be made by shuffling two shorter words together while keeping the letters of each one in order.2D dynamic programming
  60. 60Maximum Length of Pair ChainPick the most pairs that can follow one another, where each pair must start after the last one ended.Greedy by sorting