Command Palette

Search for a command to run...

Hectal

Module 28

DP Foundations: 1D

Dynamic programming from scratch: memoisation, tabulation, the five-step recipe, take-or-skip decisions, and the classic 1D problems.

Intermediate 4 lessons 8 problems ~50 min of lessons
1D Dynamic Programming

Dynamic programming (DP) is recursion that remembers. When a recursive solution keeps solving the same smaller problems again and again, storing each answer the first time turns an exponential algorithm into a linear one.

This module builds the habit step by step. You'll see the waste in plain recursion, fix it with memoisation, rewrite it bottom-up as a table, shrink the table to a few variables, and then use one recipe (state, transition, base cases, order, answer) on the classic 1D problems: stairs, robbers, decodings, word breaks and products.

Best after: Recursion

Part 1

Learn the ideas

  1. 28.1From Recursion to MemoisationIf a recursive function is called with the same arguments many times, cache each result the first time it's computed. The work drops to (number of distinct states) × (work per state).14 min
  2. 28.2Tabulation and the Five-Step RecipeBottom-up DP fills a table from the smallest states upward. Write down state, transition, base cases, order and answer before coding.14 min
  3. 28.3Take-or-Skip DecisionsMany 1D problems ask, at each item, whether to use it. dp[i] = best of (skip item i) and (take item i plus the best compatible earlier state).12 min
  4. 28.4Recognising a DP ProblemCount the ways, find the min or max, or decide yes or no over choices that interact, especially when greedy fails and brute force branches exponentially.8 min

Part 2

Solve the problems

In order of difficulty. Each one shows the pattern it teaches.

  1. 28.1Climbing StairsEasy1D Dynamic Programming

    The first DP: ways(i) = ways(i − 1) + ways(i − 2).

  2. 28.2Min Cost Climbing StairsEasy1D Dynamic Programming

    Switching from counting to minimising: same shape, min instead of +.

  3. 28.3House RobberMedium1D Dynamic Programming

    Take-or-skip: dp[i] = max(dp[i − 1], dp[i − 2] + nums[i]).

  4. 28.4House Robber IIMedium1D Dynamic Programming

    Break a circle into two lines: exclude the first house or exclude the last.

  5. 28.5Delete and EarnMedium1D Dynamic Programming

    Transforming a problem into House Robber by bucketing values.

  6. 28.6Decode WaysMedium1D Dynamic Programming

    Counting with validity checks: one-digit and two-digit transitions, careful with zeros.

  7. 28.7Word BreakMedium1D Dynamic Programming

    A yes/no DP over prefixes: can the first i characters be split into dictionary words?

  8. 28.8Maximum Product SubarrayMedium1D Dynamic Programming

    Carrying two states: a negative number turns the smallest product into the largest.