Skip to content
Sign inGet Started

DP · written course

Dynamic programming, from a slow recursion to a fast table

Solving a hard problem by remembering the easy ones.

Start reading32 pages · about 172 minutes

By the end of this course

Why some recursions never finish, how remembering answers fixes them, and how to recognise the handful of shapes that nearly every dynamic programming problem belongs to. By the end you can tell whether DP applies before writing code, define a state, write the recurrence, and say when a table is the wrong tool.

All 32 pages

  1. 1The recursion that never finished5 min read
  2. 2The two properties, checked before you write code6 min read
  3. 3Choosing what to remember6 min read
  4. 4From a state to a formula5 min read
  5. 5The cells the formula cannot fill5 min read
  6. 6Remembering what you already worked out5 min read
  7. 7Writing the recursive version first5 min read
  8. 8Turning the recursion inside out6 min read
  9. 9Turning the recursion into loops5 min read
  10. 10Throwing away the rows you no longer need5 min read
  11. 11Cutting the table down5 min read
  12. 12One decision per element6 min read
  13. 13The longest increasing subsequence, both ways6 min read
  14. 14Take it or leave it6 min read
  15. 15Can a subset hit this total5 min read
  16. 16The loop order that changes the answer5 min read
  17. 17Counting ways against fewest coins5 min read
  18. 18Two sequences and a grid6 min read
  19. 19One grid, several questions5 min read
  20. 20Turning one string into another5 min read
  21. 21Problems that work from both ends5 min read
  22. 22The grid problems, and their variations5 min read
  23. 23Splitting a range at every point5 min read
  24. 24Dynamic programming on a tree5 min read
  25. 25Counting over digits and subsets6 min read
  26. 26Buying and selling, with a state machine6 min read
  27. 27Counting is not optimising5 min read
  28. 28Getting back the answer, not just the number5 min read
  29. 29What a table costs, and when it will not fit5 min read
  30. 30The errors that do not crash6 min read
  31. 31When dynamic programming is the wrong answer6 min read
  32. 32Recognising it under pressure6 min read

Then what

Reading is the first half. When you finish, the questions for this subject test whether it went in, and every wrong option tells you why it was wrong rather than just that it was.

See the questions for DP