Dynamic Programming: 1D Problems Explained with Climbing Stairs, House Robber, and Coin Change

Why 1D DP shows up so often in interviews

If you can recognize a 1D dynamic programming problem quickly, you save a lot of time in interviews. These problems usually look simple on the surface: climb stairs, rob houses, make change, jump through an array. But the twist is that each decision depends on earlier results, and brute force repeats the same work over and over.

The good news is that many of these problems share the same structure:

• You process items in order.
• The answer at position i depends on one or more previous positions.
• You can often reduce memory from a full array to a few variables.

That is what makes 1D DP such a useful pattern. Once you learn to spot it, you can map a lot of interview questions into the same mental model.

Problem statement: what counts as a 1D DP problem?

A 1D DP problem usually has one dimension of state, often an index or a target value.

Examples:

• dp[i] = number of ways to reach step i in climbing stairs
• dp[i] = maximum money from houses 0..i in house robber
• dp[i] = minimum coins needed to make amount i in coin change

The core idea is simple:

Define what dp[i] means, figure out how dp[i] depends on earlier states, and build the answer bottom-up.

If you get the state definition right, the rest becomes much easier.

Intuition and insight

Most 1D DP problems are asking you to make a sequence of choices. At each position, you have a small number of options:

• take one step or two steps
• rob current house or skip it
• use one coin or try another coin

The trick is that the “best” answer at position i is not independent. It comes from previously solved subproblems.

A practical checklist

When you see a problem, ask:

1. What is the one-dimensional state?
2. What does dp[i] represent?
3. What previous states can lead to dp[i]?
4. What are the base cases?
5. Can I optimize space?

That’s the entire workflow.

Example 1: Climbing Stairs

Problem

You are climbing a staircase with n steps. Each move, you can climb 1 or 2 steps. How many distinct ways can you reach the top?

Why this is DP

To get to step i, you must come from:

• step i - 1 by taking 1 step
• step i - 2 by taking 2 steps

So the number of ways to reach i depends on the previous two values.

State definition

Let dp[i] be the number of ways to reach step i.

Then:

dp[i] = dp[i - 1] + dp[i - 2]

This is the Fibonacci pattern.

Base cases

• dp[0] = 1 — there is one way to stand at the start
• dp[1] = 1 — only one way to reach step 1

Bottom-up Python solution

def climb_stairs(n: int) -> int:
    if n <= 1:
        return 1

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

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

Walkthrough

Suppose n = 5.

• dp[0] = 1
• dp[1] = 1
• dp[2] = 2
• dp[3] = 3
• dp[4] = 5
• dp[5] = 8

So there are 8 ways to climb 5 stairs.

Space-optimized version

You only need the last two values.

def climb_stairs_optimized(n: int) -> int:
    if n <= 1:
        return 1

    prev2, prev1 = 1, 1

    for _ in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current

    return prev1

This is a good example of a common 1D DP refinement: once you understand the recurrence, you can compress the state.

Example 2: House Robber

Problem

You are given a list of non-negative integers, where each value represents the amount of money in a house. You cannot rob two adjacent houses. Find the maximum amount you can rob.

Why this is DP

At each house, you have two choices:

• rob it, which means you must skip the previous house
• skip it, which means you keep the best result from the previous house

State definition

Let dp[i] be the maximum money you can rob from houses 0..i.

Then:

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

Meaning:

• dp[i - 1] = skip current house
• dp[i - 2] + nums[i] = rob current house

Base cases

• dp[0] = nums[0]
• dp[1] = max(nums[0], nums[1])

Bottom-up Python solution

def rob(nums: list[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

    return dp[-1]

Walkthrough

For nums = [2, 7, 9, 3, 1]:

• dp[0] = 2
• dp[1] = 7
• dp[2] = max(7, 2 + 9) = 11
• dp[3] = max(11, 7 + 3) = 11
• dp[4] = max(11, 11 + 1) = 12

Answer: 12

Space-optimized version

Again, you only need the last two states.

def rob_optimized(nums: list[int]) -> int:
    prev2 = 0  # dp[i - 2]
    prev1 = 0  # dp[i - 1]

    for num in nums:
        current = max(prev1, prev2 + num)
        prev2, prev1 = prev1, current

    return prev1

This version is often easier to code once you understand the recurrence.

Example 3: Coin Change

Problem

Given coin denominations and a target amount, find the minimum number of coins needed to make that amount. Return -1 if it is not possible.

Why this is DP

This is a 1D target-based DP. Instead of building up an index in an array of houses or stairs, you build up an amount.

For each amount i, you try all coin choices and see which previous state leads to the best answer.

State definition

Let dp[i] be the minimum number of coins needed to make amount i.

Then:

dp[i] = min(dp[i - coin] + 1 for each coin if i - coin >= 0)

Base case

• dp[0] = 0
• All other values start as infinity because they are initially unreachable

Bottom-up Python solution

def coin_change(coins: list[int], amount: int) -> int:
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return -1 if dp[amount] == INF else dp[amount]

Walkthrough

For coins = [1, 2, 5] and amount = 11:

• dp[0] = 0
• dp[1] = 1
• dp[2] = 1
• dp[3] = 2
• dp[4] = 2
• dp[5] = 1
• dp[6] = 2
• dp[7] = 2
• dp[8] = 3
• dp[9] = 3
• dp[10] = 2
• dp[11] = 3

Answer: 3 because 11 = 5 + 5 + 1

Important note

Coin change is different from climbing stairs in one key way:

• climbing stairs asks for the number of ways
• coin change asks for the minimum cost

Same pattern, different objective.

How to build a 1D DP solution in interviews

Here is the process I recommend.

1) Define the state clearly

Write a sentence:

• dp[i] is the number of ways to reach step i
• dp[i] is the max money from the first i houses
• dp[i] is the minimum coins to make amount i

If you cannot define the state in one sentence, pause and fix that first.

2) Identify the transition

Ask what previous states can lead to i.

Examples:

• i - 1 and i - 2 for climbing stairs
• i - 1 and i - 2 for house robber
• i - coin for coin change

3) Set base cases

Your recurrence cannot work without correct starting values.

Common patterns:

• dp[0] = 1 for counting ways
• dp[0] = 0 for counting cost
• dp[0] = nums[0] or similar for max problems

4) Choose iteration order

For most 1D DP, you build from smaller states to larger states.

Ask:

• Does dp[i] depend only on smaller indices?
• Can I compute left to right?

If yes, bottom-up DP is usually the cleanest.

5) Optimize space if possible

If dp[i] depends only on a small number of previous values, you can replace the array with a few variables.

This often helps in interviews, because it shows you understand the recurrence rather than just memorizing an array solution.

Complexity analysis

Here is a quick comparison of the examples above.

What to say in an interview

You can summarize these patterns like this:

• Climbing stairs and house robber are linear scans with fixed-size dependencies.
• Coin change is still 1D DP, but the state space is target-based instead of index-based.
• Space optimization is possible when each state depends on only a few previous states.

Common mistakes to avoid

1) Confusing the meaning of dp[i]

If you define the state loosely, the recurrence becomes messy. Be precise.

2) Getting base cases wrong

A lot of incorrect answers come from bad initialization, not bad transitions.

3) Mixing up counting and optimization

Counting problems usually use addition. Optimization problems usually use min or max.

4) Forgetting unreachable states

In coin change, initialize with infinity so you can detect impossible amounts.

5) Overcomplicating the solution

If the problem is linear and only depends on a few prior states, you probably do not need recursion plus memoization unless it helps clarity.

Related problems to practice

Once you understand 1D DP, these problems become much easier:

• Fibonacci Number
• Min Cost Climbing Stairs
• Maximum Subarray
• Longest Increasing Subsequence
• Decode Ways
• Partition Equal Subset Sum
• Unique Paths with obstacles in a 1D optimization setup

Many of these are just variations on the same idea: define a useful state, write the recurrence, and build from the base case.

Key takeaways

• 1D DP works well when the answer at i depends on earlier states in one dimension.
• Start by defining dp[i] clearly in one sentence.
• Derive the recurrence from the allowed transitions.
• Use correct base cases; they matter as much as the formula.
• Optimize space when the recurrence only needs a few prior values.
• Climbing stairs, house robber, and coin change are classic interview examples of the same pattern.

If you want to trace the state changes visually, I built an interactive version of this walkthrough at codebrew.ai — might help if you are a visual learner.

Practice these next

1. Min Cost Climbing Stairs
2. Decode Ways
3. House Robber II
4. Coin Change II
5. Maximum Product Subarray