题解 | #最小花费爬楼梯#
最小花费爬楼梯
https://www.nowcoder.com/practice/6fe0302a058a4e4a834ee44af88435c7
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param cost int整型vector * @return int整型 */ int minCostClimbingStairs(vector<int>& cost) { // write code here int n = cost.size(); vector<int> f(n + 1); f[0] = f[1] = 0; // 从0或者1的阶梯上花费都为0 for (int i = 2; i <= n; i++) { f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]); } return f[n]; } };
- 思路:动态规划
- 状态表示:f(i)表示跳到第i个台阶需要的最小代价
- 状态计算:f(i)有上一次跳一个台阶或者跳两个台阶的状态转移,f(i) = min(f(i - 1) + cost(i - 1), f(i - 2) + cost(i - 2))
- 时间复杂度:O(n)
- 空间复杂度:O(n)