746 使用最小花费爬楼梯
唯一需要注意的是初始化:
可以从第0阶或第1阶楼梯出发,说明到达这两阶楼梯不需要花费
因此dp[0]和dp[1]都为0,而不是cost[0]和cost[1]
正常版
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1);
dp[0] = 0;
dp[1] = 0;
// dp[i] 表示到达第i个台阶的最低花费
for(int i = 2; i <= n; i++){
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[n];
}
};
时间复杂度:\(O(n)\)
空间复杂度:\(O(n)\)
优化版
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(2);
dp[0] = 0;
dp[1] = 0;
int res;
// dp[i] 表示到达第i个台阶的最低花费
for(int i = 2; i <= n; i++){
res = min(dp[1] + cost[i - 1], dp[0] + cost[i - 2]);
dp[0] = dp[1];
dp[1] = res;
}
return res;
}
};
时间复杂度:\(O(n)\)
空间复杂度:\(O(1)\)