easy1D Dynamic Programming

Min Cost Climbing Stairs

Each stair has a cost paid when you leave it. Start at index 0 or 1 and move one or two steps at a time. Find the minimum cost to reach just beyond the final stair.

LeetCode ↗

Work through the cases

3 examples

Input notation

At least two nonnegative stair costs separated by spaces.

Expected result

The minimum total cost.

Case 1

Input

10 15 20

Expected output

Case 2

Input

1 100 1 1

Expected output

Case 3

Input

0 0

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Start at index 0 or 1, pay the current stair, and climb one or two steps. n ≤ 1000; plain recursion repeats stairs. The cost from i depends only on i+1 and i+2; past the top it is 0. Memoization computes each index once. The answer is \min(dfs(0), dfs(1)). Time and space O(n).

We design a function dfs(i), which represents the minimum cost required to climb the stairs starting from the i-th step. Therefore, the answer is \min(dfs(0), dfs(1)).

The execution process of the function dfs(i) is as follows:

- If i ≥ len(cost), it means the current position has exceeded the top of the stairs, and there is no need to climb further, so return 0; - Otherwise, we can choose to climb 1 step with a cost of cost[i], then recursively call dfs(i + 1); or we can choose to climb 2 steps with a cost of cost[i], then recursively call dfs(i + 2); - Return the minimum cost between these two options.

To avoid repeated calculations, we use memoization search, saving the results that have already been calculated in an array or hash table.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array cost.

class Solution {
    private Integer[] f;
    private int[] cost;

    public int minCostClimbingStairs(int[] cost) {
        this.cost = cost;
        f = new Integer[cost.length];
        return Math.min(dfs(0), dfs(1));
    }

    private int dfs(int i) {
        if (i >= cost.length) {
            return 0;
        }
        if (f[i] == null) {
            f[i] = cost[i] + Math.min(dfs(i + 1), dfs(i + 2));
        }
        return f[i];
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.