Min Cost Climbing Stairs

NeetCode: Min Cost Climbing Stairs · LeetCode: 746. Min Cost Climbing Stairs · Difficulty: Easy

cost[i] is the price of stepping off stair i. Once you pay it you may climb one or two stairs. You may start on stair 0 or stair 1. Return the minimum cost to reach the top, which is one position past the last stair.

Example

Text

Input:  cost = [10, 15, 20]                              Output: 15
Input:  cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]      Output: 6

Brute force: recursion from each start

Let f(i) be the minimum cost to reach the top when standing on stair i (before paying for it). Standing at or beyond the top costs nothing; otherwise pay cost[i] and take the cheaper of the two moves. The answer is min(f(0), f(1)).

Java

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

    public int minCostClimbingStairs(int[] cost) {
        return Math.min(f(cost, 0), f(cost, 1));
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minCostClimbingStairs(new int[]{10, 15, 20}));
        System.out.println(solution.minCostClimbingStairs(new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1}));
    }
}

Output

15
6

Each call makes two branches and the subproblems overlap. Time: O(2^n). Space: O(n) recursion stack.

Optimal: bottom-up with two variables

Let dp[i] be the minimum cost to arrive at position i. Positions 0 and 1 are free starts. To arrive at i you either came from i - 1 (paying cost[i - 1]) or from i - 2 (paying cost[i - 2]), so dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]). The answer is dp[n]. Only the last two entries are ever read.

Java

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int twoBack = 0; // dp[0]
        int oneBack = 0; // dp[1]
        for (int i = 2; i <= cost.length; i++) {
            int cur = Math.min(oneBack + cost[i - 1], twoBack + cost[i - 2]);
            twoBack = oneBack;
            oneBack = cur;
        }
        return oneBack;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minCostClimbingStairs(new int[]{10, 15, 20}));
        System.out.println(solution.minCostClimbingStairs(new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1}));
        System.out.println(solution.minCostClimbingStairs(new int[]{5, 7}));
    }
}

Output

15
6
5

Time: O(n). Space: O(1). For [10, 15, 20]: dp = [0, 0, 10, 15], so the answer is 15 (start on stair 1, pay 15, jump to the top).