Skip to content
Tutorials Center
My learning

Topics

Lesson 150 of 225 ยท Dynamic Programming

One-Dimensional DP

Practice one-dimensional dynamic programming in Python: climbing stairs, house robber, min-cost stairs, decode ways, max product subarray and jump game.

The simplest dynamic programs have a one-dimensional state: a single index i, usually "the first i items" or "ending at position i". The table is a plain list, the transition looks back a step or two, and the whole solution is often six lines. They are the best place to build intuition, and they cover a surprising share of interview questions.

This lesson works through seven classic problems. For each one we follow the same recipe from Memoization vs Tabulation: define the state in words, write the transition, set the base cases, then code it, and shrink the space where possible. Notice how the same few shapes keep returning.

Pattern 1: climbing stairs (counting ways)

You can climb a staircase of n steps taking 1 or 2 steps at a time. How many different sequences reach the top?

  • State: ways[i] = number of ways to reach step i.
  • Transition: the last move was either a 1-step from i - 1 or a 2-step from i - 2, so ways[i] = ways[i-1] + ways[i-2].
  • Base: ways[0] = 1 (do nothing), ways[1] = 1.

That is Fibonacci in disguise. The brute force makes the same exponential tree as plain Fibonacci (see Dynamic Programming).

TEXT
n = 4:  1+1+1+1   1+1+2   1+2+1   2+1+1   2+2     -> 5 ways
Python Climbing stairs: brute force and DP

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The general version, sum(ways[i - s] for s in steps), handles any set of allowed step sizes. It is the template for counting problems.

Pattern 2: house robber (take or skip)

A row of houses holds cash nums[i]. You may not rob two neighbouring houses. What is the most you can take?

Brute force: every house is "robbed" or "skipped", with no two adjacent robbed: roughly 1.6^n valid choices, still exponential.

  • State: best[i] = maximum loot using only the first i houses.
  • Transition: for house i (the i-th, 1-based) either skip it (best[i-1]) or rob it and use the best from two houses back (best[i-2] + nums[i-1]): best[i] = max(best[i-1], best[i-2] + nums[i-1]).
  • Base: best[0] = 0, best[1] = nums[0].

Because we only look back two steps, two variables suffice.

Python House robber

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the loop, take is "best total if I rob this house", which can only extend a total where the previous house was skipped. The pair (skip, take) replaces the whole table. A greedy "always rob the biggest house" fails on [4, 5, 4]: it grabs the 5 and has to leave both neighbours, for a total of 5, while robbing the two outer houses gives 8.

A variant, house robber II, puts the houses in a circle (first and last are neighbours). Run the linear solution twice: once without the first house, once without the last, and take the better.

Pattern 3: minimum cost climbing stairs (best of two)

Each step i has a cost cost[i] to leave. You may start on step 0 or 1 and climb 1 or 2 steps at a time. What is the cheapest way to get past the last step (to the "top" at index n)?

  • State: dp[i] = minimum cost to stand on position i (positions 0..n, where n is the top).
  • Transition: you arrive from i - 1 paying cost[i-1], or from i - 2 paying cost[i-2]: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]).
  • Base: dp[0] = dp[1] = 0 (starting is free).
Python Minimum cost climbing stairs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the second example the cheapest route steps on every 1 and hops over every 100, for a total of 6. The table makes the logic visible: each entry is the cheaper of two predecessors plus their exit fee.

Pattern 4: decode ways (counting with conditions)

A message of digits encodes letters: 1 -> A, 2 -> B, ..., 26 -> Z. Given a digit string, how many ways can it be decoded? For "226" the answers are 2|2|6 (BBF), 22|6 (VF) and 2|26 (BZ): 3 ways.

  • State: ways[i] = number of ways to decode the first i digits.
  • Transition: the last piece is either a single digit (valid if it is 1..9, i.e. not 0) or a two-digit number (valid if 10..26): ways[i] = (ways[i-1] if s[i-1] != '0') + (ways[i-2] if 10 <= int(s[i-2:i]) <= 26).
  • Base: ways[0] = 1 (empty prefix), and ways[1] = 0 if the first digit is '0', else 1.
TEXT
s = "226"
ways[0] = 1
ways[1] ("2")   = 1
ways[2] ("22")  = ways[1] ("2|2") + ways[0] ("22")        = 2
ways[3] ("226") = ways[2] ("..|6") + ways[1] ("2|26")     = 3
Python Decode ways

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The zeros are the interesting part: "10" has one decoding (J), "06" has none because a leading zero is not a letter, and "2101" has one (2|10|1). This is the template for counting problems with local validity rules.

Pattern 5: maximum product subarray (two states)

In the Kadane lesson you found the best sum of a contiguous run. For products, negatives flip the sign: a very negative running product becomes very positive after the next negative number. So a single running value is not enough; track both the maximum and minimum product of a subarray ending at the current index.

  • State: hi[i], lo[i] = largest and smallest product of a subarray ending at i.
  • Transition: hi[i] = max(x, hi[i-1]*x, lo[i-1]*x), lo[i] = min(x, hi[i-1]*x, lo[i-1]*x) where x = nums[i].
  • Answer: the maximum hi[i] seen anywhere.
Python Maximum product subarray

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The brute force is O(n^2); the DP is O(n) time and O(1) space. For [-2, 3, -4] the answer 24 uses the whole array: lo held -6 until the -4 turned it positive.

Pattern 6: jump game (reachability)

Each nums[i] is the maximum jump length from index i. Can you reach the last index starting at 0? As a DP: reachable[i] is true if some earlier reachable j has j + nums[j] >= i. That is O(n^2). Noticing that you only need the farthest index reachable so far gives O(n) and is really a greedy sweep (see greedy problems); both views are useful.

Python Jump game: table and farthest reach

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Pattern 7: more counting patterns (painting a fence, three-move stairs, broken steps)

Counting problems come in many costumes. Here are three more that reuse the same recipe: define the state in words, then say how the last move could have happened.

Painting a fence. A fence has n posts and you have k colours. You may not paint three or more adjacent posts the same colour. How many colourings are there? The state needs one extra fact about the last post: does it match the one before it?

  • same[i]: colourings of i posts where post i has the same colour as post i - 1. That can only extend a colouring where post i - 1 was different from i - 2, so same[i] = diff[i - 1].
  • diff[i]: colourings where post i differs from post i - 1. Any colouring of i - 1 posts works, and there are k - 1 other colours: diff[i] = (same[i - 1] + diff[i - 1]) * (k - 1).

Three-move stairs (tribonacci). With steps of 1, 2 or 3, ways[i] = ways[i-1] + ways[i-2] + ways[i-3], and three rolling variables are enough.

Broken steps. Some steps are broken and cannot be stood on. The only change to the recurrence is that ways[i] = 0 for a broken step.

Python Painting a fence, tribonacci stairs and broken steps

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For three posts and two colours, 6 of the 8 colourings are legal (only AAA and BBB are banned). The fence DP needs O(n) time and O(1) space. Whenever you see "no more than two in a row", the pair of states same as before / different from before is the standard answer; for longer runs, see the bounded-run DP in Word Wrap, Box Stacking and Tile Stacking.

The shape of 1-D DP

All seven problems fit a handful of shapes:

Shape Transition looks like Problems
Count ways dp[i] = dp[i-a] + dp[i-b] + ... stairs, decode ways
Take or skip dp[i] = max(dp[i-1], dp[i-2] + value) house robber
Best of predecessors dp[i] = min(dp[j] + cost for j in options) min cost stairs
Track extremes ending here keep best and worst so far max product
Reachability dp[i] = any(dp[j] and ...) jump game
Count with a run limit two states: same as before / different painting a fence

Complexity is nearly always O(n) time (n states, constant work each) and O(1) space after rolling the table down to the last one or two entries. When each state loops over earlier states (jump game DP), the time becomes O(n^2).

Common mistakes

  • Off-by-one between positions and items. Decide whether dp[i] means "first i items" (size n + 1) or "item i" (size n) and stay consistent.
  • Wrong base cases for tiny inputs. Test the empty list, one element, and two elements (rob([]), rob([5])).
  • Forgetting invalid cases such as the digit 0 in decode ways.
  • Using one running value for max product; you need the minimum as well.
  • Reading old values after a tuple update. Python's a, b = b, a + b evaluates the right side first; writing it in two statements needs a temporary variable.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. For climbing stairs with steps of 1 or 2, which recurrence is correct?

    The last move is a 1-step from i-1 or a 2-step from i-2, and the counts of ways add.
  2. 2. In house robber, what does best[i] = max(best[i-1], best[i-2] + nums[i-1]) express?

    Robbing house i forbids house i-1, so we can only build on the best result of the first i-2 houses.
  3. 3. Why does maximum product subarray track the minimum product as well?

    Multiplying a very negative running product by another negative gives a large positive one.
  4. 4. How many ways can "226" be decoded with 1->A ... 26->Z?

    2|2|6, 22|6 and 2|26 are the valid splits.
  5. 5. What are the usual time and space of a 1-D DP whose transition looks back a constant number of steps?

    There are n states with constant work each; only the last few entries are ever needed, so space shrinks to O(1).

Summary

  • One-dimensional DP has a state like "the first i items" or "ending at index i", stored in a list.
  • Counting problems add predecessor counts; optimisation problems take a min or max over a few predecessors.
  • Stairs, house robber, min-cost stairs and decode ways all need only the last one or two entries, so space becomes O(1).
  • Max product subarray tracks both the largest and the smallest product ending at each index.
  • Painting a fence tracks two states (same colour as the previous post, or different); tribonacci stairs and broken steps are small tweaks of the stairs recurrence.
  • Jump game shows a DP whose O(n^2) table collapses to an O(n) sweep with the farthest reach.
  • Always test tiny inputs and special values like zero.

Next: The 0/1 Knapsack Problem