Loop

1-D Dynamic Programming

From Fibonacci to LIS: caching overlapping subproblems along one dimension.

0 of 6 lessons complete · 162 min total

Start module
  1. DP: Recursion With a MemorySpotting overlapping subproblems, top-down memoization vs bottom-up tables, defining the state and recurrence, and the 'how many ways / min-max over sequential decisions' signals.Lesson · 18 minNot completed
  2. Filling the 1-D TableEach cell built from the cells before it.Animation · 10 minNot completed
  3. Practice: Fibonacci & Robber FamilyTwo-step recurrences and the rob-or-skip decision, including the circular variant.easy×2medium×24 problems · 0 solvedPractice · 35 minNot completed
  4. Practice: Strings & CoinsExpand-around-center palindromes, digit decodings, and the unbounded-knapsack coin minimum.medium×44 problems · 0 solvedPractice · 45 minNot completed
  5. Practice: Subsequences & PartitionsSign-flip products, dictionary segmentation, LIS, and subset-sum to half.medium×44 problems · 0 solvedPractice · 45 minNot completed
  6. 1-D DP CheckpointState definition, recurrence derivation, memo vs tabulation, and space optimization.Checkpoint · 9 minNot completed