Min Cost Climbing Stairs

​On a staircase, every ith step is associated with some non-negative cost cost[i]. Once you pay the cost, you can either climb one or two steps. You need to find the minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.

Example 1:

Input: cost[] = {2, 5, 3, 1, 7, 3, 4}
Output: 9 
Steps: 2->3->1->3

Example 2:

Input: cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1}
Output: 6
Steps: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

Note:

  1. cost will have a length in the range [2, 1000].
  2. Every cost[i] will be an integer in the range [0, 999].

There is a clear recursion available: the final cost dp[i] to climb the staircase from some step i is 

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

This motivates dynamic programming.

Algorithm: 

Let dp[i] be the cost to climb the ith staircase to from 0th or 1st step. Hence:

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

Since dp[i-1] and dp[i-2] are needed to compute the cost of travelling from ith step, a bottom-up approach can be used to solve the problem. The answer will be the minimum cost of reaching n-1th stair and n-2th stair. Compute the dp[] array in a bottom-up manner. Below is the implementation of the above approach.

public int minCostClimbingStairs(int[] cost) {

    if (cost == null || cost.length == 0) {
        return 0;
    }
    int len = cost.length;
    if (len == 1) return cost[0];
    if (len == 2) return Math.min(cost[0], cost[1]);

    int[] dp = new int[len];
    dp[0] = cost[0];
    dp[1] = cost[1];

    for (int i = 2; i < cost.length; i++) {
        dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
    }
    return Math.min(dp[len - 2], dp[len - 1]);
}

Complexity Analysis

  • Time Complexity: O(N) where N is the length of cost.
  • Space Complexity: O(N), the space used by dp.

The problem can also be solved in O(1) space without a dp array and using some constant variables.

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        if (cost == null || cost.length == 0) return 0;
        int f1 = cost[0];
        int f2 = cost[1];
        for (int i = 2; i < cost.length; i++) {
            int f3 = cost[i] + Math.min(f1, f2);
            f1 = f2;
            f2 = f3;
        }
        return Math.min(f1, f2);
    }
}

Categories: Dynamic Programming

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s