Skip to content
Python Central Hub

One Dimensional DP

Most “easy-to-medium” DP interview questions share one shape: the state is a single index ii — usually “position in the array” or “position in the string” — and dp[i]dp[i] answers “what’s the best result considering everything up to (or starting at) index ii?” Once you can write that one sentence, the recurrence almost always falls out of it.

What you’ll learn

  • Why the state for these problems is just dp[i]dp[i] — one integer, no extra dimensions.
  • Five classic 1D problems, each with its recurrence in math and a runnable solution: Climbing Stairs, House Robber, House Robber II, Coin Change (both variants), and Decode Ways.
  • How circular constraints (House Robber II) reduce to two calls of the linear version.
  • Space optimization: most of these only need the last one or two dpdp values, not the whole array.

The state: dp[i]dp[i]

For every problem below, dp[i]dp[i] means “the best answer considering arr[0..i]arr[0..i]” — and the transition asks: given dp[i-1]dp[i-1] and dp[i-2]dp[i-2] (or similar), how do I get dp[i]dp[i]? Write that sentence first, every time, before touching code.

Climbing Stairs

You can climb 1 or 2 steps at a time. How many distinct ways are there to reach step nn? Reaching step ii means your last hop was either 1 step from i - 1i - 1 or 2 steps from i - 2i - 2 — so the count at ii is the sum of both.

dp[i]=dp[i−1]+dp[i−2],dp[0]=1, dp[1]=1dp[i] = dp[i-1] + dp[i-2], \quad dp[0] = 1,\ dp[1] = 1
climbing_stairs.py
def climb_stairs(n):
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1     # dp[i-2], dp[i-1]
    for i in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1
 
 
print(climb_stairs(5))    # expect 8
print(climb_stairs(10))   # expect 89
climbing_stairs.py
def climb_stairs(n):
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1     # dp[i-2], dp[i-1]
    for i in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1
 
 
print(climb_stairs(5))    # expect 8
print(climb_stairs(10))   # expect 89

This is literally Fibonacci wearing a different costume — and it already uses the O(1) space trick: only the last two values are ever needed, so there’s no reason to keep a full array.

House Robber

Rob houses in a row for maximum total loot, but you can’t rob two adjacent houses. At house ii, you either skip it (carry dp[i-1]dp[i-1] forward) or rob it (take nums[i]nums[i] plus the best from dp[i-2]dp[i-2], since i-1i-1 is now off-limits).

dp[i]=max⁡(dp[i−1], dp[i−2]+nums[i])dp[i] = \max\big(dp[i-1],\ dp[i-2] + nums[i]\big)
house_robber.py
def rob(nums):
    prev2, prev1 = 0, 0     # dp[i-2], dp[i-1]
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1
 
 
print(rob([2, 7, 9, 3, 1]))   # expect 12  (2 + 9 + 1)
print(rob([1, 2, 3, 1]))      # expect 4   (1 + 3)
house_robber.py
def rob(nums):
    prev2, prev1 = 0, 0     # dp[i-2], dp[i-1]
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1
 
 
print(rob([2, 7, 9, 3, 1]))   # expect 12  (2 + 9 + 1)
print(rob([1, 2, 3, 1]))      # expect 4   (1 + 3)

House Robber II (circular street)

Now the houses form a circle — house 00 and house n - 1n - 1 are adjacent too. Robbing both the first and last house is never allowed together, so the answer is the better of two linear sub-problems: “rob houses 0..n-20..n-2” or “rob houses 1..n-11..n-1”. Reuse the exact function above, twice.

house_robber_ii.py
def rob_linear(nums):
    prev2, prev1 = 0, 0
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1
 
 
def rob_circular(nums):
    if len(nums) == 1:
        return nums[0]
    exclude_last = rob_linear(nums[:-1])    # never touch the last house
    exclude_first = rob_linear(nums[1:])    # never touch the first house
    return max(exclude_last, exclude_first)
 
 
print(rob_circular([2, 3, 2]))       # expect 3
print(rob_circular([1, 2, 3, 1]))    # expect 4
house_robber_ii.py
def rob_linear(nums):
    prev2, prev1 = 0, 0
    for num in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + num)
    return prev1
 
 
def rob_circular(nums):
    if len(nums) == 1:
        return nums[0]
    exclude_last = rob_linear(nums[:-1])    # never touch the last house
    exclude_first = rob_linear(nums[1:])    # never touch the first house
    return max(exclude_last, exclude_first)
 
 
print(rob_circular([2, 3, 2]))       # expect 3
print(rob_circular([1, 2, 3, 1]))    # expect 4

Coin Change: minimum coins

Given coin denominations and a target amount, find the fewest coins that sum to it (or report it’s impossible). Here the state is the amount itself: dp[a]dp[a] is the minimum coins needed to make amount aa. For each amount, try using one more of every coin and take the best.

dp[a]=1+min⁡c ∈ coins, c≤adp[a−c],dp[0]=0dp[a] = 1 + \min_{c \,\in\, coins,\ c \le a} dp[a - c], \qquad dp[0] = 0
coin_change_min.py
def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1
 
 
print(coin_change([1, 2, 5], 11))    # expect 3  (5 + 5 + 1)
print(coin_change([2], 3))           # expect -1 (impossible)
coin_change_min.py
def coin_change(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1
 
 
print(coin_change([1, 2, 5], 11))    # expect 3  (5 + 5 + 1)
print(coin_change([2], 3))           # expect -1 (impossible)

Coin Change II: count the ways

Same coins, same amount, but now count how many distinct combinations make that amount (order doesn’t matter — {1,2}\{1, 2\} and {2,1}\{2, 1\} are the same combination). The trick that stops double-counting: loop coins on the outside, amounts on the inside, so each coin is only ever “added” after the ones before it in the list have already been considered.

dp[a]+=dp[a−c]for each coin c, processed one coin at a timedp[a] \mathrel{+}= dp[a - c] \quad \text{for each coin } c,\ \text{processed one coin at a time}
coin_change_ii.py
def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1                 # one way to make 0: use no coins
    for c in coins:            # coin on the OUTER loop avoids counting permutations twice
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]
 
 
print(change(5, [1, 2, 5]))   # expect 4  ({5}, {1,1,1,2}, {1,2,2}, {1,1,1,1,1})
coin_change_ii.py
def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1                 # one way to make 0: use no coins
    for c in coins:            # coin on the OUTER loop avoids counting permutations twice
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]
 
 
print(change(5, [1, 2, 5]))   # expect 4  ({5}, {1,1,1,2}, {1,2,2}, {1,1,1,1,1})

Decode Ways

A digit string encodes letters ("1""1" -> A … "26""26" -> Z). Count the number of ways to decode it. dp[i]dp[i] is the number of ways to decode the first ii characters: it inherits dp[i-1]dp[i-1] if the single digit at i-1i-1 is valid (11-99), and also inherits dp[i-2]dp[i-2] if the two-digit number ending at i-1i-1 is valid (1010-2626).

dp[i]=dp[i−1]⋅[ s[i−1]≠’0’ ]⏟single digit+ dp[i−2]⋅[ 10≤int(s[i−2:i])≤26 ]⏟two digitsdp[i] = \underbrace{dp[i-1] \cdot [\,s[i-1] \ne \text{'0'}\,]}_{\text{single digit}} +\ \underbrace{dp[i-2] \cdot [\,10 \le \text{int}(s[i-2:i]) \le 26\,]}_{\text{two digits}}
decode_ways.py
def num_decodings(s):
    if not s or s[0] == "0":
        return 0
    n = len(s)
    prev2, prev1 = 1, 1    # dp[0] = 1 (empty prefix), dp[1] = 1 (first char is valid)
    for i in range(2, n + 1):
        current = 0
        if s[i - 1] != "0":                       # single digit s[i-1] is valid (1-9)
            current += prev1
        two_digit = int(s[i - 2:i])
        if 10 <= two_digit <= 26:                  # two digits s[i-2:i] are valid (10-26)
            current += prev2
        prev2, prev1 = prev1, current
    return prev1
 
 
print(num_decodings("226"))   # expect 3  ("2,2,6" / "22,6" / "2,26")
print(num_decodings("06"))    # expect 0  (leading zero can't be decoded)
decode_ways.py
def num_decodings(s):
    if not s or s[0] == "0":
        return 0
    n = len(s)
    prev2, prev1 = 1, 1    # dp[0] = 1 (empty prefix), dp[1] = 1 (first char is valid)
    for i in range(2, n + 1):
        current = 0
        if s[i - 1] != "0":                       # single digit s[i-1] is valid (1-9)
            current += prev1
        two_digit = int(s[i - 2:i])
        if 10 <= two_digit <= 26:                  # two digits s[i-2:i] are valid (10-26)
            current += prev2
        prev2, prev1 = prev1, current
    return prev1
 
 
print(num_decodings("226"))   # expect 3  ("2,2,6" / "22,6" / "2,26")
print(num_decodings("06"))    # expect 0  (leading zero can't be decoded)

Filling the table, one index at a time

sketch 1D dp array filling left to right (Climbing Stairs) p5.js
dp[i] only ever needs dp[i-1] and dp[i-2] -- once those two are known, every later cell is O(1) to compute.

Practice — real LeetCode problems

House Robber is the canonical “take it or skip it” one-dimensional DP, and it is asked constantly. Do all three in order: the second adds a circular constraint you handle by running the first one twice, and the third replaces the numeric choice with a choice over a dictionary.

LC 198 — House Robber · Medium

Problem. Each house on a street holds nums[i]nums[i] in cash, but robbing two adjacent houses triggers the alarm. Return the maximum you can take.

Constraints. 1 <= len(nums) <= 1001 <= len(nums) <= 100, 0 <= nums[i] <= 4000 <= nums[i] <= 400.

Examples. [1,2,3,1][1,2,3,1] gives 44 (houses 0 and 2) · [2,7,9,3,1][2,7,9,3,1] gives 1212 (houses 0, 2 and 4)

Editorial · approach, complexity, follow-ups

The state is “the best I can do considering the first ii houses”, split by whether house ii was robbed. Splitting on the last decision is the same move that derived Climbing Stairs; here the decision carries a value.

Time O(n)O(n). Space O(1)O(1).

The textbook single-array form is dp[i] = max(dp[i-1], dp[i-2] + nums[i])dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — either skip house ii and keep dp[i-1]dp[i-1], or rob it and add dp[i-2]dp[i-2]. The two-variable version is that with the table thrown away.

  • Greedy fails. Taking the largest remaining house and discarding its neighbours is wrong on [3,4,3][3,4,3]: the greedy grabs the 4, which blocks both 3s, for a total of 4 — the answer is 6. Have that counterexample ready; interviewers ask why a local choice is not enough.
  • [2,1,1,2][2,1,1,2] = 4 is the discriminating case for the tuple update. If you assign taketake and then compute skipskip from the new taketake, you allow adjacent houses and get 6.
  • Single house must return nums[0]nums[0], and the loop handles it because both accumulators start at 0.
  • All zeros returns 0, and no house is ever forced.

Follow-ups you should expect: “Which houses?” — keep a parent array or rerun the decision backwards. “Circular street?” — LC 213, next. “A binary tree instead of a street?” — LC 337, in the Tree DP page. “No two houses within kk?” — the recurrence becomes max(dp[i-1], dp[i-k-1] + nums[i])max(dp[i-1], dp[i-k-1] + nums[i]). “Must rob exactly kk houses?” — add kk as a second dimension.

LC 213 — House Robber II · Medium

Problem. Same rule, but the houses form a circle — the first and last are adjacent. Return the maximum.

Constraints. 1 <= len(nums) <= 1001 <= len(nums) <= 100, 0 <= nums[i] <= 10000 <= nums[i] <= 1000.

Examples. [2,3,2][2,3,2] gives 33 (you cannot take both 2s now) · [1,2,3,1][1,2,3,1] gives 44

Editorial · approach, complexity, follow-ups

You cannot fix a circular dependency inside one left-to-right pass, because the decision at index 0 constrains index n-1n-1, which you have not reached yet. The standard escape is to enumerate the thing that closes the loop — here, whether house 0 is robbed — and solve a linear problem for each case.

Note the two runs are not “exclude first” and “exclude last” as an exhaustive partition of plans; they overlap, and that is fine. What matters is that every valid circular plan is feasible in at least one run, and every plan feasible in a run is valid on the circle.

Time O(n)O(n), two passes. Space O(1)O(1).

  • Length 1 must be special-cased. nums[:-1]nums[:-1] and nums[1:]nums[1:] are both empty, so the helper returns 0 and you would answer 0 instead of nums[0]nums[0].
  • Length 2 works without a special case: one slice holds each house, and the answer is the max. Worth checking, because many solutions guard len < 3len < 3 unnecessarily.
  • [2,3,2][2,3,2] = 3 is the case that separates this from LC 198. If you get 4 you are still solving the linear version.

Follow-ups you should expect: “Why exactly two runs?” — because there is one adjacency to break and two ways to break it. “Circular maximum subarray sum (LC 918)?” — same trick: either the answer is a normal Kadane result, or it wraps, which means the complement is a minimum subarray. “Robber on a cycle of length 1?” — the special case above. “Robber on a general graph?” — that is maximum weight independent set, NP-hard; trees and cycles are the tractable cases.

LC 139 — Word Break · Medium

Problem. Given a string ss and a dictionary wordDictwordDict, decide whether ss can be segmented into a sequence of one or more dictionary words. Words may be reused.

Constraints. 1 <= len(s) <= 3001 <= len(s) <= 300, 1 <= len(wordDict) <= 10001 <= len(wordDict) <= 1000, words are distinct, lowercase letters only.

Examples. s = "leetcode", wordDict = ["leet","code"]s = "leetcode", wordDict = ["leet","code"] gives TrueTrue · s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] gives FalseFalse

Editorial · approach, complexity, follow-ups

One-dimensional DP over prefixes of a string rather than over an array of numbers. dp[i]dp[i] answers a yes/no question about s[:i]s[:i], and the transition asks where the last word started.

Time O(n2⋅L)O(n^2 \cdot L) where LL is the average word length — n2n^2 split points, and each slice-and-hash costs O(L)O(L). Space O(n)O(n) plus the set.

  • dp[0] = Truedp[0] = True is the base case. Without it nothing is ever reachable and everything returns FalseFalse.
  • Greedy longest-match fails. On "catsandog""catsandog" with ["cats","dog","sand", "and","cat"]["cats","dog","sand", "and","cat"], taking "cats""cats" first leaves "andog""andog", which dead-ends. The DP also tries "cat""cat" + "sand""sand" — and that dead-ends too, which is why the answer is FalseFalse. This single case kills both the greedy and any solution that returns early on the first failed branch.
  • Reuse is allowed, so "applepenapple""applepenapple" is fine with two "apple""apple"s. Nothing in the recurrence forbids it — which is exactly why an unbounded-style DP is the right model.
  • The breakbreak is correctness-neutral but a real speedup: you only need one valid split.

Two useful refinements. Bound the inner loop by the longest dictionary word instead of scanning to 0. Or replace the set with a trie and walk forward from each dp[j]dp[j] that is TrueTrue, which avoids building substrings at all — the answer to “what if the dictionary is enormous?”

Follow-ups you should expect: “Return one valid segmentation?” — store the split point that worked and walk back. “Return all segmentations (LC 140)?” — exponentially many, so memoized backtracking, not a boolean table. “Count the segmentations?” — replace the boolean with a sum; the loop stops breaking early. “Why not BFS over indices?” — that works and is the same graph, with dpdp as the visited set.

LeetCode problem set

#ProblemDifficultyThe twist
70Climbing StairsEasyThe exact template above
198House RobberMediumLinear adjacency constraint
213House Robber IIMediumCircular version, solved as two linear calls
322Coin ChangeMediumMinimum coins to reach an amount
518Coin Change IIMediumCount the distinct combinations instead
91Decode WaysMediumA 1-or-2-step lookback on a digit string
139Word BreakMediumdp[i]dp[i] = “can the first ii characters be segmented into dictionary words?”, checking every valid split point

Recap

  • The state for these problems is one index: dp[i]dp[i] means “the best answer using/considering everything up through position ii.”
  • Climbing Stairs and House Robber both look back exactly 2 positions — the same shape as Fibonacci with a different combine step.
  • House Robber II’s circular constraint reduces to two linear calls, each excluding one endpoint.
  • Coin Change minimizes over choices (minmin + 1 per coin); Coin Change II counts combinations by looping coins on the outside to avoid counting the same set in a different order.
  • Decode Ways looks back 1 or 2 positions depending on whether the single digit or the two-digit pair is a valid letter code.
  • Whenever the lookback is a fixed, small number of steps, drop the full dpdp array for O(1) space — just carry the last few values forward.

Next: Two Dimensional DP and Knapsack — states with two indices, starting with the 0/1 knapsack and its rolling-array space optimization.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Was this page helpful?

Let us know how we did