Min Cost Climbing Stairs

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Minimum cost to reach top of stairs where you can climb 1 or 2 steps. DP.

Algorithm

1dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Answer = min(dp[n-1], dp[n-2]).

Common Pitfalls

•Same as LC 746. Can start from step 0 or step 1. DP is O(n) O(1) with two variables.

Min Cost Climbing Stairs.java

Java

// Approach: DP. dp[i] = min cost to reach step i = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]).
// Time: O(n) Space: O(1)
class Solution {
    static int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];

        Arrays.fill(dp, -1);

        return solve(cost, 0, dp);
    }

    static int solve(int[] cost, int i, int[] dp) {
        if (dp[i] != -1)
            return dp[i];

        if (i == cost.length - 1)
            return 0;

        if (i == cost.length - 2)
            return Math.min(cost[i + 1], cost[i]);

        int n1 = cost[i] + solve(cost, i + 1, dp);

        int n2 = cost[i + 1] + solve(cost, i + 2, dp);

        dp[i] = Math.min(n1, n2);

        return dp[i];
    }
};

Was this solution helpful?