leetcode 746. Min Cost Climbing Stairs

这道题用动态规划解决。这道题乍一看，含义有点模糊。有两个点要搞清楚：1）给定len个台阶的梯子，其实是要爬完（越过）整个梯子才算到达顶部，相当于顶部是第len+1层台阶。台阶序号从0开始编号的话，顶部就是第len个台阶。2）从第i个台阶往上爬，才需要支付cost[i]。如果站在第i个台阶没有继续往上爬，则不需要支付const[i]。这样才好理解，dp[0]和dp[1]的值为什么是0。

第一版不带注释

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

写完注释后，发现当len等于2的情形，其实不需要单独考虑，后面的代码可以涵盖这种情况。

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int len = cost.size();//题目已经保证len>=2// if(len < 3) return min(cost[0],cost[1]);//给定的len层的梯子，楼顶其实是第len+1层vector<int> dp(len+1);//dp[i]表示到达第i层台阶所需要的最低花费dp[0] = 0;//含义是从第0层出发，爬0层就到达了第0层，不需要支付dp[1] = 0;//含义是从第1层出发，爬0层就到达了第1层，不需要支付//给定的len层的梯子，楼顶其实是第len+1层，但是由于从0开始编号，所以i应该取到lenfor(int i = 2;i <= len;i++){//到达第i层，有两种可能，要么是从第i-1层爬一个台阶到达的，//要么是从第i-2层爬两个台阶到达的dp[i] = min(cost[i-1]+dp[i-1],cost[i-2]+dp[i-2]);}return dp[len];}
};

进一步优化空间开销。因为计算dp[i]只需要dp[i-1]和dp[i-2]，所以可以去掉dp数组，改用两个变量，如代码所示：

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {int len = cost.size();//题目保证len>=2,所以下面的i从2开始起算int dp_i_2 = 0;//表示到达第i-2层所需的最小花费int dp_i_1 = 0;//表示到达第i-1层所需的最小花费int dp_i = 0;  //表示到达第i层所需要的最小花费for(int i = 2;i <= len;i++){dp_i = min(dp_i_1+cost[i-1],dp_i_2+cost[i-2]);dp_i_2 = dp_i_1;dp_i_1 = dp_i;}return dp_i;}
};