# 题目描述
# 思路与题解
这个题目描述的比较绕，如果有纸和笔的话，在纸上画一画会好很多，比如我胡乱画的如下
看了官方题解，思路才比较清晰了
上述代码的时间复杂度和空间复杂度都是 O (n)。但也可以用滚动数组的方式将空间复杂度优化到 O (1)
class Solution { | |
public: | |
int minCostClimbingStairs(vector<int>& cost) { | |
int n = cost.size(); | |
int res[n+1]; | |
res[0] = res[1] = 0; | |
res[2] = cost[0] < cost[1] ? cost[0] : cost[1]; | |
int r1, r2; | |
for (int i = 2; i < n; ++i) { | |
r1 = res[i-1] + cost[i-1]; | |
//r2 = res[i-1] + cost[i-1] + cost[i]; | |
r2 = res[i-2] + cost[i-2] + cost[i]; | |
res[i+1] = r1 < r2 ? r1 : r2; | |
} | |
return res[n]; | |
} | |
}; |
class Solution { | |
public: | |
int minCostClimbingStairs(vector<int>& cost) { | |
int n = cost.size(); | |
int prev = 0, curr = 0; | |
for (int i = 2; i <= n; ++i) { | |
int next = min(curr + cost[i-1], prev + cost[i-2]); | |
prev = curr; | |
curr = next; | |
} | |
return curr; | |
} | |
}; |
