How to Compute the Min Cost of Climbing Stairs via Dynamic Progr

  • 时间:2020-09-24 11:41:27
  • 分类:网络文摘
  • 阅读:102 次

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) —

推荐阅读:
子产却楚逆女以兵原文及翻译  伏羲洞游记  玩游戏的感受作文700字  不一样的母亲节作文  走在毕业路的中途  支教书法心得  写人作文小贾作文  读《凡卡》有感作文1200字  雨后校园作文300字  我的夜,我的人间的十二月天 
评论列表
添加评论