Skip to content
AI360Xpert
Back to 1-D Dynamic Programming
Easy

Min Cost Climbing Stairs

You are given an integer array `cost` where `cost[i]` is the cost of `ith` step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index `0`, or the step with index `1`. Return the minimum cost to reach the top of the floor.

Examples

Input:cost = [10,15,20]
Output:15
You will start at index 1. - Pay 15 and climb two steps to reach the top. The total cost is 15.
Input:cost = [1,100,1,1,1,100,1,1,100,1]
Output:6
You will start at index 0. - Pay 1 and climb two steps to reach index 2. - Pay 1 and climb two steps to reach index 4. - Pay 1 and climb two steps to reach index 6. - Pay 1 and climb one step to reach index 7. - Pay 1 and climb two steps to reach index 9. - Pay 1 and climb one step to reach the top. The total cost is 6.

Constraints

  • 2 <= cost.length <= 1000
  • 0 <= cost[i] <= 999

Dynamic Programming (Space Optimized)

Approach

To reach step `i` (where the top floor is index `n`), you can come from step `i-1` or `i-2`. The minimum cost to reach step `i` is the minimum of the cost to reach step `i-1` plus `cost[i-1]`, and the cost to reach step `i-2` plus `cost[i-2]`. We can iterate through the array maintaining only the costs of the last two steps. At the end, the minimum cost to reach the top is the minimum of the two accumulated values.

Complexity Analysis

Time Complexity
O(n)
Space Complexity
O(1)

Time complexity is O(n) because we iterate through the array once. Space complexity is O(1) as we only use two variables to store previous states.

Solution.java
class Solution {    public int minCostClimbingStairs(int[] cost) {        int n = cost.length;                // Cost to reach the first two steps is 0 (we can start at 0 or 1)        int prev1 = 0; // step i-2        int prev2 = 0; // step i-1                for (int i = 2; i <= n; i++) {            int currentCost = Math.min(prev1 + cost[i - 2], prev2 + cost[i - 1]);            prev1 = prev2;            prev2 = currentCost;        }                return prev2;    }}