On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).

Once you pay the cost, you can either climb one or two steps. You need to find 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 = [10, 15, 20]
Output: 15
Explanation: Cheapest is start on cost[1], pay that cost and go to the top.

Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
Output: 6
Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].

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

Stair Climbing Algorithm using Dynamic Programming

First of all, the stairs have no directions – which means that we can solve the problem in two directions, bottom up or top down. It is like simple stair climbing problem with uniform cost equal to one – and the answer is Fibonacci numbers!

Similarly, the Dynamic Programming equation is:

1

f[i] = min(f[i-1], f[i-2]) + cost[i];

f[i] = min(f[i-1], f[i-2]) + cost[i];

where f[i] is the cost of climbing up to current stair i and the cost[i] is the current stair cost. The final answer will be min(f[n-1], f[n-2]) where n-1 and n-2 are the last two stairs. If you DP in other direction, the final answer will be min(f[0], f[1]) respectively.

As, we can modify the original stair costs array, thus, allowing us to save the intermediate DP values.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        if (n == 0) return 0;
        if (n == 1) return cost[0];
        for (int i = 2; i < n; ++ i) {
            cost[i] = min(cost[i - 1], cost[i - 2]) + cost[i];
        }
        return min(cost[n - 2], cost[n - 1]);
    }
};

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n = cost.size();
        if (n == 0) return 0;
        if (n == 1) return cost[0];
        for (int i = 2; i < n; ++ i) {
            cost[i] = min(cost[i - 1], cost[i - 2]) + cost[i];
        }
        return min(cost[n - 2], cost[n - 1]);
    }
};

The above C++ Dynamic Programming implementation runs at O(N) time and O(1) constant space if we don’t count the inputs. A better DP solution will be use two variables to store the intermediate cost value, iteratively.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int f2 = 0, f1 = 0;
        for (const auto &n: cost) {
            int cur = n + min(f2, f1);
            f2 = f1;
            f1 = cur;
        }
        return min(f1, f2);
    }
};

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int f2 = 0, f1 = 0;
        for (const auto &n: cost) {
            int cur = n + min(f2, f1);
            f2 = f1;
            f1 = cur;
        }
        return min(f1, f2);
    }
};

Same O(N) time, but O(1) constant space. You can also use Breadth First Search or Depth First Search algorithm to solve this puzzle, neither is optimial w.r.t the time complexity unless the intermediate results are cached which is possible.

–EOF (The Ultimate Computing & Technology Blog) —