Dynamic Programming

1-D Dynamic Programming

State depends on a single index: climbing stairs, house robber, decode ways.

Medium, about 90 minutes to practise.

1Understand

The idea

Define dp[i] as the answer for the first i elements (or for the input ending at i), then write how it is built from a few earlier values, such as dp[i] = max(dp[i−1], dp[i−2] + a[i]). Set the base cases, fill the table in order, and keep only the last few values when that is all the recurrence uses.

Intuition

Define dp[i] as the answer for a prefix (or for a subproblem ending at i), then write how it builds from a few earlier values, e.g. dp[i] = max(dp[i-1], dp[i-2] + a[i]).

Set base cases carefully, fill in increasing order, and keep only the last few values when the recurrence allows. If overlapping subproblems and optimal substructure are present, DP beats exponential recursion.

Name what dp[i] means in words before coding; wrong definitions are the usual failure.

What you will be able to do

  • Define the state in words
  • Write the recurrence and base cases
  • Reduce memory to O(1)

When to use it

  • Number of ways to reach step n
  • Best total without taking adjacent items
  • Answer for i depends on a few previous answers

2See it

Walkthrough

Climbing stairs

n = 4, dp[i] = dp[i−1] + dp[i−2].

1 / 4

1
1
?
?
?
01234

dp[0]=1 (one way to stay), dp[1]=1. Or base dp[1]=1, dp[2]=2 depending on indexing.

dp = [0]*(n+1); dp[0]=1; dp[1]=1

Live template

Line 1 active

1dp = [0] * (n + 1); dp[0] = base
2for i in range(1, n + 1):
3 dp[i] = best_of(dp[i - 1], dp[i - 2] + value(i))
4return dp[n]

Complexity: time O(n), space O(n) → O(1)

Time O(n), space O(n) or O(1) with rolling. Memoised recursion is the same asymptotics with more overhead. Greedy "always take largest" fails here, DP is required.

Read the walkthrough as text

House robber. nums = [2,7,9,3,1].

  1. dp[i] = max money using houses up to i.
  2. Transition: rob i → dp[i-2] + nums[i]; skip i → dp[i-1].
  3. Bases: dp[0]=2, dp[1]=max(2,7)=7.
  4. Then 9 → max(7, 2+9)=11, 3 → max(11,7+3)=11, 1 → max(11,11+1)=12.

Rolling vars prev2, prev1 replace the array when only two prior states matter.

3Recognise it

Kinds of problems (10)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Counting ways (climbing stairs)

    Example. Number of ways to climb n stairs taking 1 or 2 steps.

    How. dp[i] = dp[i−1] + dp[i−2]; only the last two values matter.

  • Take / skip (house robber)

    Example. Max money from houses in a line without adjacent picks.

    How. dp[i] = max(dp[i−1], dp[i−2] + nums[i]); skip vs take.

  • Decode ways

    Example. Number of ways to decode a digit string as letters A-Z.

    How. dp[i] depends on whether s[i] alone and s[i−1..i] as a pair are valid codes.

  • Word break

    Example. Can you segment s into dictionary words?

    How. dp[i] is true if some earlier dp[j] is true and s[j:i] is a word.

  • Maximum subarray (Kadane)

    Example. Largest sum of any contiguous subarray.

    How. At each index, either extend the previous run or start fresh: best_ending = max(x, best_ending + x).

  • Maximum product subarray

    Example. Largest product of a contiguous subarray (negatives flip signs).

    How. Track both max and min product ending here; a negative can turn the min into the new max.

  • Look back over a fixed set of distances (ticket passes)

    Example. Cheapest set of day/week/month passes to cover travel days.

    How. dp[day] = min cost covering up to that day; look back 1 / 7 / 30 from each travel day.

  • Memo on large n with jumps

    Example. Reach the end with jump lengths from each index (or frog jump).

    How. State is position (and sometimes last jump); memoise reachable states instead of re-exploring.

  • Probability with a sliding sum

    Example. Probability of total points in a range with dice / continuous draws.

    How. dp[i] from a window of prior outcomes; maintain a sliding sum of the last W probabilities.

  • Maximum circular subarray

    Example. Max subarray sum when the array wraps around.

    How. Answer is max(Kadane, total, min-subarray); handle the all-negative case carefully.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Exponential recursion

    Why it happens. The recursive tree looks simple until overlapping subproblems explode.

    How it fails. Climbing stairs with plain fib(n): fib(40) recomputes fib(38) twice and times out; with memo it is 40 states.

    Fix. Cache by state (`@cache` or a dp table). Each distinct index (or tuple) should be computed once.

  • Wrong base case

    Why it happens. Off-by-one on empty / first positions quietly shifts every later cell.

    How it fails. House robber with dp[0] = 0 instead of nums[0]: the recurrence never “takes” the first house correctly.

    Fix. State the meaning of dp[i] in words, then set every base that the recurrence reads before the main loop.

  • State not defined

    Why it happens. Filling an array named dp without defining what each cell means makes the recurrence guesswork.

    How it fails. Mixing “best ending at i” with “best using first i items” in one formula, neither recurrence holds.

    Fix. Write one sentence: “dp[i] = …”. Derive the transition only from that definition.

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons