2026-2-9：LeetCode每日一题（动态规划专项）

爬代价楼梯

题目描述：

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

难于昨天的楼梯

昨天的爬楼梯https://blog.ZEEKLOG.net/2401_87095818/article/details/157910173?fromshare=blogdetail&sharetype=blogdetail&sharerId=157910173&sharerefer=PC&sharesource=2401_87095818&sharefrom=from_link

解法一：（递归版）

源码：

class Solution { int n1(int n, vector<int>& cost, vector<int>& vis) { if (n > 2) { if (vis[n] != 0) { return vis[n]; } else { vis[n] = min(n1(n - 1, cost, vis) + cost[n - 1], n1(n - 2, cost, vis) + cost[n - 2]); return vis[n]; } } else { if (n == 1) { return 0; } else { return min(cost[0], cost[1]); } } } public: int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); vector<int> vis(n + 1); return n1(n, cost, vis); } };

说明：

超时了

解法二：

源码：

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

说明：

递归太耗时了，循环替代。

解法三：

源码：

class Solution { int n1(int n, vector<int>& cost) { if (n == 1) return 0; if (n == 2) return min(cost[0], cost[1]); int a = 0; // 对应vis[1] int b = min(cost[0], cost[1]); // 对应vis[2] int res = 0; for (int i = 3; i <= n; i++) { res = min(b + cost[i - 1], a + cost[i - 2]); a = b; b = res; } return res; } public: int minCostClimbingStairs(vector<int>& cost) { int n = cost.size(); return n1(n, cost); } };

说明:

去掉数组，进一步压缩空间

总结

递归超时有3个主要原因：

1.函数调用栈的硬开销（主要原因）

递归的每一次调用，系统都需要：

• 为函数创建栈帧（保存返回地址、参数、局部变量）；
• 把参数（n、cost、vis）从当前函数复制到新函数；
• 函数执行完成后，销毁栈帧并返回结果；

2.缓存访问的开销

递归函数中存在一些判断，多次调用多次判断

3.系统对递归的限制

操作系统对函数栈的深度有上限，超出会直接触发栈溢出错误，而迭代没有这个限制