1D DP Problems - Learning Module

Loading content...

0/276

Climbing Stairs Variations

Fibonacci in Disguise: The Climbing Stairs Problem

The Climbing Stairs problem is perhaps the most famous DP interview question, appearing in countless technical interviews at companies from startups to FAANG. It seems entirely different from Fibonacci at first glance — you're climbing stairs, making choices, counting distinct paths. But beneath the surface, it's Fibonacci wearing a different costume.

The classic problem statement:

You are climbing a staircase with n steps. Each time you can climb either 1 step or 2 steps. In how many distinct ways can you climb to the top?

This problem introduces a crucial DP concept: counting the number of ways to reach a state by summing the ways to reach all predecessor states that can transition to it.

What You Will Learn

By the end of this page, you will: (1) Recognize Climbing Stairs as Fibonacci in disguise, (2) Understand how DP counts paths through state space, (3) Generalize to k-step variations, (4) Handle problems with variable costs, (5) Apply minimum/maximum cost climbing variants, (6) Master variations with constraints and forbidden steps.

The Basic Climbing Stairs Problem

Let's work through the classic Climbing Stairs problem step by step, building the DP solution from first principles.

Problem Analysis:

Imagine you're at step 0 (the ground) and want to reach step n. At each moment, you choose to take 1 step or 2 steps. The question is: how many different sequences of choices lead you to exactly step n?

The Key Insight:

To reach step n, you must have come from either:

Step (n-1), then took a 1-step jump
Step (n-2), then took a 2-step jump

These are the only two ways to arrive at step n. Therefore:

ways(n) = ways(n-1) + ways(n-2)

This is literally the Fibonacci recurrence! The ways to reach step n is the sum of ways to reach the two predecessor steps.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Climbing Stairs — Classic DP Problem
 * 
 * Problem: How many distinct ways can you climb n stairs,
 * taking 1 or 2 steps at a time?
 * 
 * Recurrence: ways(n) = ways(n-1) + ways(n-2)
 * Base cases: ways(0) = 1 (one way to stay at ground), ways(1) = 1
 * 
 * Time: O(n), Space: O(1)
 */
function climbStairs(n: number): number {
    // Base cases: 
    // - ways(0) = 1: "Do nothing" is one valid way to be at step 0
    // - ways(1) = 1: Only one way to reach step 1 (single 1-step)
    if (n <= 1) return 1;
    
    // Same space-optimized pattern as Fibonacci
    let prev2 = 1;  // ways(0)
    let prev1 = 1;  // ways(1)
    
    for (let i = 2; i <= n; i++) {
        const current = prev1 + prev2;  // ways(i) = ways(i-1) + ways(i-2)
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}
 
// Verification with small examples:
// n=1: [1] → 1 way
// n=2: [1,1], [2] → 2 ways
// n=3: [1,1,1], [1,2], [2,1] → 3 ways
// n=4: [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2] → 5 ways
 
console.log(climbStairs(1));  // 1
console.log(climbStairs(2));  // 2
console.log(climbStairs(3));  // 3
console.log(climbStairs(4));  // 5
console.log(climbStairs(5));  // 8  (Fibonacci sequence: 1,1,2,3,5,8...)

Why ways(0) = 1?

This is a subtle but important point. There is exactly one way to "climb" zero stairs: do nothing. This isn't a trick — it's the multiplicative identity for counting. When we sum paths, the empty path must count as 1, not 0, otherwise our recurrence breaks.

Think of it this way: from step 2, you can reach it by:

Starting from step 0, climb 2 (that's 1 way, using the 1 path to reach step 0)
Starting from step 1, climb 1 (that's 1 way, using the 1 path to reach step 1)

Total: 2 ways. If ways(0) were 0, we'd get 1 way, which is wrong.

The Mapping to Fibonacci

climbStairs(n) = F(n+1), where F is the standard Fibonacci sequence. The sequences are: Fibonacci: 0,1,1,2,3,5,8,13... | Climbing Stairs: 1,1,2,3,5,8,13... | They're offset by one position because of different base case conventions.

Understanding the State Space

To truly master climbing stairs (and all DP problems), we must understand the concept of state space and how DP counts paths through it.

What is a State?

In DP, a state represents a position in the problem space that captures all information needed to solve the subproblem from that point forward. For climbing stairs:

State: The current step number (0, 1, 2, ..., n)
State space: All possible states {0, 1, 2, ..., n}
Goal state: Step n
Transitions: From state i, you can move to state i+1 (1-step) or i+2 (2-step)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
State Space Graph (directed, from left to right):
 
    ┌──────────────┐
    │   1-step     │
    │   jumps      ↓
  [0] ──→ [1] ──→ [2] ──→ [3] ──→ [4] ──→ [5]
    │      │       │       │       │       │
    │      │       │       │       │      END
    └──────┘       │       │       │
    2-step jump    └───────┘       │
                   2-step jump     └───────┘
                                   2-step jump
 
All possible paths from [0] to [5]:
1. 0→1→2→3→4→5  (five 1-steps)
2. 0→1→2→3→5    (three 1-steps, one 2-step)
3. 0→1→2→4→5    (two 1-steps, one 2-step, one 1-step)
4. 0→1→3→4→5    (one 1-step, one 2-step, two 1-steps)
5. 0→1→3→5      (one 1-step, two 2-steps)
6. 0→2→3→4→5    (one 2-step, three 1-steps)
7. 0→2→3→5      (one 2-step, one 1-step, one 2-step)
8. 0→2→4→5      (two 2-steps, one 1-step)
 
Total: 8 distinct paths (which equals climbStairs(5))

The Counting Principle:

DP counts paths through state space using the additive principle:

The number of ways to reach state S = sum of (ways to reach each predecessor state P × ways to transition from P to S)

For climbing stairs, each transition has exactly 1 way (you either take 1 step or 2 steps), so:

ways(n) = ways(n-1) × 1 + ways(n-2) × 1 = ways(n-1) + ways(n-2)

This generalizes beautifully. If there were 3 ways to take a 1-step (e.g., left foot, right foot, both feet), the recurrence would be:

ways(n) = 3 × ways(n-1) + ways(n-2)

DP = Counting Paths in a DAG

Many counting DP problems can be visualized as 'count all paths from source to destination in a directed acyclic graph (DAG)'. The states are nodes, transitions are edges. DP exploits the DAG structure: process nodes in topological order, and each node's count is the sum of its predecessors' counts.

Generalization: K Steps at a Time

The basic climbing stairs problem allows 1 or 2 steps. What if you could take up to k steps at a time? This generalization reveals the pattern's flexibility.

Problem: K-Step Climbing

You can climb 1, 2, 3, ..., or k steps at a time. In how many distinct ways can you reach step n?

The recurrence extends naturally:

ways(n) = ways(n-1) + ways(n-2) + ways(n-3) + ... + ways(n-k)

Or more formally: ways(n) = Σ ways(n-i) for i = 1 to min(k, n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
 * K-Step Climbing Stairs
 * 
 * Problem: Climb n stairs taking 1, 2, ..., or k steps at a time.
 * 
 * Recurrence: ways(n) = sum of ways(n-i) for i in 1..k
 * Base case: ways(0) = 1
 * 
 * Time: O(n × k)
 * Space: O(k) with sliding window optimization
 */
function climbStairsK(n: number, k: number): number {
    if (n === 0) return 1;
    if (k <= 0) return 0;
    
    // DP table: dp[i] = number of ways to reach step i
    const dp: number[] = new Array(n + 1).fill(0);
    dp[0] = 1;  // Base case: one way to be at step 0
    
    for (let i = 1; i <= n; i++) {
        // Sum all predecessor states within k steps
        for (let j = 1; j <= Math.min(k, i); j++) {
            dp[i] += dp[i - j];
        }
    }
    
    return dp[n];
}
 
// Space-optimized version using sliding window
function climbStairsKOptimized(n: number, k: number): number {
    if (n === 0) return 1;
    if (k <= 0) return 0;
    
    // Only keep the last k values
    const window: number[] = new Array(k).fill(0);
    window[0] = 1;  // ways(0) = 1, stored at window[0 % k]
    
    let windowSum = 1;  // Maintain running sum for O(1) updates
    
    for (let i = 1; i <= n; i++) {
        // The new value is the sum of the window
        const newValue = windowSum;
        
        // Update window: remove oldest, add newest
        const oldestIndex = i % k;
        const oldest = window[oldestIndex];
        window[oldestIndex] = newValue;
        
        // Update running sum: remove old value, add new value
        windowSum = windowSum - oldest + newValue;
    }
    
    return window[n % k];
}
 
// Examples:
console.log(climbStairsK(4, 2));  // 5 (same as basic problem)
console.log(climbStairsK(4, 3));  // 7 (can now take 3-step jumps)
console.log(climbStairsK(4, 4));  // 8 (can jump directly to step 4)
console.log(climbStairsK(4, 10)); // 8 (k > n, so effectively k = n)

Climbing Stairs Values for Different k
n	k=2	k=3	k=4	k=∞ (all steps)
1	1	1	1	1
2	2	2	2	2
3	3	4	4	4
4	5	7	8	8
5	8	13	15	16
6	13	24	29	32

Special Case: k = ∞

When k ≥ n, you can jump directly from step 0 to any step. This means ways(n) = 2^(n-1) for n ≥ 1. Each step except the last has two choices: either land on it or skip it. The last step must be landed on.

Variable Step Sizes — Custom Allowed Jumps

A more interesting variant allows specific step sizes rather than 1 through k. This is closer to real-world problems like making change with specific coin denominations.

Problem: Custom Steps

Given a set of allowed step sizes (e.g., {1, 3, 5}), in how many ways can you climb n stairs?

This is equivalent to counting the number of ways to make sum n using values from a set, where order matters.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * Climbing Stairs with Custom Allowed Steps
 * 
 * Problem: Given allowed step sizes, count ways to reach step n.
 * 
 * This is equivalent to counting ordered combinations (sequences)
 * that sum to n using values from the steps array.
 * 
 * Time: O(n × steps.length)
 * Space: O(n)
 */
function climbStairsCustom(n: number, steps: number[]): number {
    // Validate input
    const validSteps = steps.filter(s => s > 0 && Number.isInteger(s));
    if (validSteps.length === 0 || n < 0) return 0;
    if (n === 0) return 1;
    
    // DP table
    const dp: number[] = new Array(n + 1).fill(0);
    dp[0] = 1;
    
    // For each position, sum contributions from all valid predecessors
    for (let i = 1; i <= n; i++) {
        for (const step of validSteps) {
            if (i >= step) {
                dp[i] += dp[i - step];
            }
        }
    }
    
    return dp[n];
}
 
// Examples with interesting step sets:
console.log(climbStairsCustom(6, [1, 2]));     // 13 (standard problem)
console.log(climbStairsCustom(6, [1, 3, 5]));  // 8
console.log(climbStairsCustom(6, [2, 3]));     // 1 (only 2+2+2 or 3+3)
console.log(climbStairsCustom(6, [2]));        // 1 (only 2+2+2)
console.log(climbStairsCustom(7, [2]));        // 0 (impossible!)
 
// The [2,3] case is interesting: limited options
// 6 = 2+2+2 = 3+3, but order matters, so each distinct sequence counts:
// Actually: 2+2+2, 2+2+2, 3+3, 3+3... wait let me recalculate
// dp[0]=1, dp[1]=0, dp[2]=1, dp[3]=1, dp[4]=1, dp[5]=1, dp[6]=2
console.log(climbStairsCustom(6, [2, 3]));     // 2 (corrected)

Connection to Coin Change:

This problem is closely related to the coin change problem:

Climbing stairs with custom steps: Order matters (1+2 ≠ 2+1)
Coin change counting combinations: Order doesn't matter (1+2 = 2+1)

The difference lies in the DP table filling order:

Ordered (Climbing Stairs): Outer loop on steps, inner loop on positions — or vice versa
Unordered (Coin Combinations): Outer loop on coins, inner loop on amounts (to avoid counting permutations)

Order of Loops Matters!

In climbing stairs, we iterate over positions first (for i in 1..n), then over steps — this counts ordered sequences. In coin change combinations, we iterate over coins first — this counts unordered sets. The mathematical difference is subtle but the results differ dramatically.

Minimum Cost Climbing Stairs

Moving from counting to optimization: instead of counting how many ways to climb, we ask what's the minimum cost to climb.

Problem: Minimum Cost Climbing Stairs (LeetCode 746)

Each step i has a cost cost[i]. Starting from step 0 or step 1, pay the cost of the step to move 1 or 2 steps up. What is the minimum cost to reach the top (beyond the last step)?

This transforms our recurrence from addition (counting paths) to minimization (optimization).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/**
 * Minimum Cost Climbing Stairs
 * 
 * LeetCode 746: Classic optimization DP problem.
 * 
 * State: minCost[i] = minimum cost to reach step i
 * Recurrence: minCost[i] = min(minCost[i-1], minCost[i-2]) + cost[i]
 * Goal: Reach beyond the last step, so answer is min(minCost[n-1], minCost[n-2])
 * 
 * Time: O(n), Space: O(1)
 */
function minCostClimbingStairs(cost: number[]): number {
    const n = cost.length;
    
    if (n === 0) return 0;
    if (n === 1) return cost[0];
    
    // Base cases: can start at step 0 or step 1 for free
    // minCost to REACH step 0 = 0, but we pay cost[0] to LEAVE step 0
    // Think of it as: to leave step i, you pay cost[i]
    
    // Alternative interpretation: minCost[i] = minimum cost to be able to 
    // climb from step i (i.e., have paid cost[i])
    
    let prev2 = cost[0];  // Min cost to be able to climb from step 0
    let prev1 = cost[1];  // Min cost to be able to climb from step 1
    
    for (let i = 2; i < n; i++) {
        // To climb from step i, we need to:
        // 1. Reach step i (coming from step i-1 or i-2)
        // 2. Pay cost[i]
        const current = Math.min(prev1, prev2) + cost[i];
        prev2 = prev1;
        prev1 = current;
    }
    
    // To reach the top (beyond last step), we can jump from 
    // either the last step (index n-1) or second-to-last (index n-2)
    return Math.min(prev1, prev2);
}
 
// Alternative: Tabulation with clear DP array
function minCostClimbingStairsTabulated(cost: number[]): number {
    const n = cost.length;
    if (n === 0) return 0;
    if (n === 1) return cost[0];
    
    // dp[i] = minimum cost to reach the top starting from step i
    // (Working backwards from the goal)
    const dp: number[] = new Array(n);
    
    // Base cases: from last two steps, cost to reach top is just their cost
    dp[n - 1] = cost[n - 1];
    dp[n - 2] = cost[n - 2];
    
    // Fill backwards
    for (let i = n - 3; i >= 0; i--) {
        dp[i] = cost[i] + Math.min(dp[i + 1], dp[i + 2]);
    }
    
    // Can start from step 0 or step 1
    return Math.min(dp[0], dp[1]);
}
 
// Test cases
console.log(minCostClimbingStairs([10, 15, 20]));      // 15 (step 1 → top)
console.log(minCostClimbingStairs([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]));  // 6

Forward DP Approach

•State: minCost[i] = min cost to reach step i
•Direction: Build from start toward goal
•Recurrence: min(minCost[i-1], minCost[i-2]) + cost[i]
•Answer: min(minCost[n-1], minCost[n-2])

Backward DP Approach

•State: minCost[i] = min cost to reach top FROM step i
•Direction: Build from goal back to start
•Recurrence: cost[i] + min(minCost[i+1], minCost[i+2])
•Answer: min(minCost[0], minCost[1])

Forward vs Backward DP

Both approaches are valid and give the same answer. Forward DP asks 'what's the minimum cost to GET HERE?' while backward DP asks 'what's the minimum cost to GO FROM HERE to the goal?' Choose whichever feels more natural for the problem.

Path Reconstruction — Which Steps Did We Take?

DP tells us the optimal value (minimum cost, maximum ways, etc.), but often we also need the actual path that achieves that value. Path reconstruction involves tracking which choice led to each state's optimal value.

Technique: Parent Pointers or Backtracking

There are two main approaches:

Parent pointers: Store which predecessor state we came from
Backtracking: After filling the DP table, trace back from the goal by checking which predecessor would have given the optimal value

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Minimum Cost Climbing Stairs with Path Reconstruction
 * 
 * Returns both the minimum cost and the actual steps taken.
 * 
 * Time: O(n), Space: O(n) for path storage
 */
function minCostWithPath(cost: number[]): { minCost: number; path: number[] } {
    const n = cost.length;
    
    if (n === 0) return { minCost: 0, path: [] };
    if (n === 1) return { minCost: cost[0], path: [0] };
    
    // DP arrays
    const dp: number[] = new Array(n);
    const parent: number[] = new Array(n).fill(-1);
    
    dp[0] = cost[0];
    dp[1] = cost[1];
    // parent[0] and parent[1] are -1 (start positions)
    
    for (let i = 2; i < n; i++) {
        if (dp[i - 1] < dp[i - 2]) {
            dp[i] = dp[i - 1] + cost[i];
            parent[i] = i - 1;  // Came from step i-1
        } else {
            dp[i] = dp[i - 2] + cost[i];
            parent[i] = i - 2;  // Came from step i-2
        }
    }
    
    // Determine the ending step (n-1 or n-2)
    let endStep: number;
    if (dp[n - 1] < dp[n - 2]) {
        endStep = n - 1;
    } else {
        endStep = n - 2;
    }
    
    // Reconstruct path by following parent pointers
    const path: number[] = [];
    let current: number | null = endStep;
    
    while (current !== -1 && current !== null) {
        path.push(current);
        current = parent[current] === -1 ? null : parent[current];
    }
    
    path.reverse();  // We built it backwards
    
    return {
        minCost: Math.min(dp[n - 1], dp[n - 2]),
        path: path,
    };
}
 
// Example usage
const result = minCostWithPath([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]);
console.log("Minimum cost:", result.minCost);  // 6
console.log("Steps taken:", result.path);       // [0, 2, 3, 4, 6, 7, 9]
 
// Visualization of the path:
// Cost:  [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
// Index:  0   1   2  3  4   5   6  7   8   9
// Path:  [0] → [2] → [3] → [4] → [6] → [7] → [9] → TOP
// Costs:  1  +  1  +  1  +  1  +  1  +  1  +  0  = 6 (don't pay at top)
// Wait, we do pay at step 9... let me recalculate
// Starting at 0 (pay 1), jump to 2 (pay 1), to 4 (pay 1), to 6 (pay 1), 
// to 7 (pay 1), to 9 (pay 1), to top = total 6

Path Reconstruction Adds O(n) Space

If you only need the optimal value, use O(1) space. If you need the actual path, you must store either parent pointers or the full DP table for backtracking. This is a common space-value tradeoff in DP problems.

Constrained Variations — Forbidden Steps and Limits

Real-world problems often come with constraints that complicate the basic pattern. Let's explore common variations:

Variation 1: Forbidden Steps

Some steps are broken and cannot be landed on. How many ways to climb n stairs avoiding forbidden steps?

Variation 2: Maximum Consecutive Same Jumps

You cannot take more than k consecutive jumps of the same size. This adds history dependence to the state.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Climbing Stairs with Forbidden Steps
 * 
 * Problem: Some steps cannot be landed on. Count valid ways.
 * 
 * Time: O(n), Space: O(n) or O(1) with sliding window
 */
function climbWithForbidden(n: number, forbidden: Set<number>): number {
    if (forbidden.has(n)) return 0;  // Can't reach a forbidden goal
    if (n === 0) return 1;
    if (n === 1) return forbidden.has(1) ? 0 : 1;
    
    // dp[i] = ways to reach step i (0 if forbidden)
    let prev2 = forbidden.has(0) ? 0 : 1;
    let prev1 = forbidden.has(1) ? 0 : 1;
    
    for (let i = 2; i <= n; i++) {
        let current: number;
        if (forbidden.has(i)) {
            current = 0;  // Cannot land here
        } else {
            current = prev1 + prev2;  // Sum of valid predecessors
        }
        prev2 = prev1;
        prev1 = current;
    }
    
    return prev1;
}
 
// Example: Stairs 0-5, but step 2 is broken
const forbidden = new Set([2]);
console.log(climbWithForbidden(5, forbidden));  // How many ways?
 
// With step 2 forbidden:
// dp[0]=1, dp[1]=1, dp[2]=0, dp[3]=1 (only from dp[1]), 
// dp[4]=1 (only from dp[3]), dp[5]=2 (from dp[3] and dp[4])
// Paths: 0→1→3→4→5, 0→1→3→5 = 2 ways

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Climbing Stairs with Consecutive Jump Limit
 * 
 * Problem: Cannot take more than k consecutive jumps of the same size.
 * Example: With k=2, you can do 1,1,2 or 2,2,1 but not 1,1,1.
 * 
 * State: (step, lastJump, consecutiveCount)
 * This is now 3D DP!
 * 
 * Time: O(n × jumpTypes × k)
 */
function climbWithConsecutiveLimit(n: number, maxConsecutive: number): number {
    if (n === 0) return 1;
    if (maxConsecutive <= 0) return 0;
    
    // State: dp[step][lastJump][consecutiveCount]
    // lastJump: 1 or 2
    // consecutiveCount: 1 to maxConsecutive
    
    // Use memoization for clarity
    const memo = new Map<string, number>();
    
    function solve(step: number, lastJump: number, consecutive: number): number {
        if (step === n) return 1;  // Reached the goal
        if (step > n) return 0;    // Overshot
        
        const key = `${ step }, ${ lastJump }, ${ consecutive }`;
        if (memo.has(key)) return memo.get(key)!;
        
        let ways = 0;
        
        // Try 1-step jump
        if (lastJump !== 1 || consecutive < maxConsecutive) {
            const newConsec = (lastJump === 1) ? consecutive + 1 : 1;
            ways += solve(step + 1, 1, newConsec);
        }
        
        // Try 2-step jump
        if (lastJump !== 2 || consecutive < maxConsecutive) {
            const newConsec = (lastJump === 2) ? consecutive + 1 : 1;
            ways += solve(step + 2, 2, newConsec);
        }
        
        memo.set(key, ways);
        return ways;
    }
    
    // Start with no previous jump (use 0 as sentinel)
    return solve(0, 0, 0);
}
 
console.log(climbWithConsecutiveLimit(4, 2));  // Limited consecutive jumps
console.log(climbWithConsecutiveLimit(4, 10)); // 5 (effectively no limit)

Constraints Add State Dimensions

When a constraint depends on history (like 'consecutive jumps'), the state must encode that history. This increases DP dimensionality from 1D to 2D or 3D. Always ask: 'What information from the past affects my future choices?' That information must be part of the state.

Connection: From Climbing Stairs to Coin Change

Climbing stairs with custom steps is structurally identical to the coin change problem — they're the same mathematical problem with different wording.

Climbing Stairs Version:

"How many ways to climb n stairs taking steps from {1, 2}?" (Order matters: 1+2 ≠ 2+1)

Coin Change Permutations:

"How many ways to make amount n using coins {1, 2}?" (Order matters: same as climbing)

Coin Change Combinations:

"How many combinations of coins sum to n?" (Order doesn't matter: 1+2 = 2+1)

The difference between permutations and combinations lies entirely in the loop order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * Demonstration: Climbing Stairs = Coin Change Permutations
 * 
 * Both count ORDERED sequences that sum to n.
 */
 
// Climbing stairs (order matters)
function climbingStairsWays(n: number, steps: number[]): number {
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;
    
    // For each position, sum contributions from all steps
    for (let i = 1; i <= n; i++) {
        for (const step of steps) {
            if (i >= step) dp[i] += dp[i - step];
        }
    }
    
    return dp[n];
}
 
// Coin change PERMUTATIONS (order matters) — SAME as climbing stairs
function coinChangePermutations(amount: number, coins: number[]): number {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    
    // Outer loop: amounts, Inner loop: coins
    for (let i = 1; i <= amount; i++) {
        for (const coin of coins) {
            if (i >= coin) dp[i] += dp[i - coin];
        }
    }
    
    return dp[amount];
}
 
// Coin change COMBINATIONS (order doesn't matter) — DIFFERENT!
function coinChangeCombinations(amount: number, coins: number[]): number {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;
    
    // Outer loop: coins, Inner loop: amounts
    // This ensures each coin type is considered only after previous types
    for (const coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }
    
    return dp[amount];
}
 
console.log("n=4, steps={1,2}:");
console.log("Climbing (ordered):", climbingStairsWays(4, [1, 2]));      // 5
console.log("Coin Perms (ordered):", coinChangePermutations(4, [1, 2])); // 5
console.log("Coin Combs (unordered):", coinChangeCombinations(4, [1, 2])); // 3
 
// The 5 ordered ways for n=4: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2
// The 3 unordered combinations: {1,1,1,1}, {1,1,2}, {2,2}

Loop Order Determines Counting Type

Outer loop on amounts + inner loop on coins = PERMUTATIONS (ordered). Outer loop on coins + inner loop on amounts = COMBINATIONS (unordered). This is one of the most important DP patterns to memorize.

Summary and Key Takeaways

The Climbing Stairs problem family demonstrates how a single core pattern — Fibonacci recurrence — extends to a rich variety of practical problems:

Key Takeaways

•Climbing stairs is Fibonacci: ways(n) = ways(n-1) + ways(n-2) for 1 or 2 steps.
•DP counts paths through state space: Each state's count is the sum of predecessor states' counts.
•K-step generalization: ways(n) = Σ ways(n-i) for i = 1 to k, with O(k) memory optimization possible.
•Custom step sizes: Same recurrence, just sum over the allowed step set instead of 1..k.
•Optimization variants: Replace sum with min/max for minimum/maximum cost problems.
•Path reconstruction: Track parent pointers or backtrack through the DP table.
•Constrained variations: Forbidden steps set dp[i] = 0; history-dependent constraints add state dimensions.
•Connection to coin change: Identical structure — loop order determines ordered vs unordered counting.

Page Complete

You've mastered climbing stairs in all its variations. Next, we'll explore the House Robber problem — where the constraint of 'no adjacent' introduces a different kind of recurrence while maintaining the 1D DP structure.