C++刷leetcode（746. 使用最小花费爬楼梯）【动态规划】

糖逗

题目描述：

1. 数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。
   
2. 
   
3. 每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
   
4. 
   
5. 您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
   
6. 
   
7. 示例 1:
   
8. 
   
9. 输入: cost = [10, 15, 20]
   
10. 输出: 15
    
11. 解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
    
12.  示例 2:
    
13. 
    
14. 输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
    
15. 输出: 6
    
16. 解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
    
17. 注意：
    
18. 
    
19. cost 的长度将会在 [2, 1000]。
    
20. 每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。
    
21. 
    
22. 来源：力扣（LeetCode）
    
23. 链接：https://leetcode-cn.com/problems/min-cost-climbing-stairs
    
24. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int minCostClimbingStairs(vector<int>& cost) {
   
4.         int len = cost.size();
   
5.         vector<int> dp(len+1, 0);
   
6.         dp[0] = cost[0];
   
7.         dp[1] = cost[1];
   
8.         for(int i = 2; i <= len; i++){
   
9.             if(i < len)dp[i] = min(dp[i-1], dp[i-2]) + cost[i];
   
10.             else if(i == len) dp[i] = min(dp[i-1], dp[i-2]);
    
11.         }
    
12.         return dp[len];
    
13.     }
    
14. };

复制代码