题解 | 使用最小花费爬楼梯
题干分析
题设给定一个爬楼花费数组，记录每到一个台阶需要再向上爬所需的花费。要求我们求解从下标0或者1开始爬楼到达楼顶所需最小花费。
算法思路
基本的线性DP问题。根据题设我们可以假设初始我们从下标-1处出发，到下标0或者下标1，此次出发无花费。因此设数组表示到达下标为i的台阶所需花费，初始条件为：
我们的目标是到达楼顶，即求。
我们将总目标进行拆分：由于到达下下标为n的台阶只可能是从下标n-1的台阶上花费cost[n-1]上来，或者从下标n-2上花费cost[n-2]上来，我们取其中的最小值，由此DP状态转移方程为：
同时我们不难观测到整个DP状态转移过程只涉及相邻的三个DP状态，完全可以优化空间为并使用迭代完成。
实现代码
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int a = 0, b = 0; // b为到达当前台阶所需最小花费，a为到达b下面一个台阶的最小花费
for (int i = 1; i < cost.size(); ++i) {
// 这里似乎和状态转移方程有所出入，
// 主要是因为状态转移方程所在视角为目标（此实现下为i+1）
// 而此迭代实现时站在中间台阶视角。因此循环也是在计算完n-1后结束
int tmp = min(a + cost[i - 1], b + cost[i]);
a = b;
b = tmp;
}
return b;
}
};
复杂度分析
- 时间复杂度：每个台阶迭代计算一次，时间复杂度为
- 空间复杂度：常数额外空间，空间复杂度为
字节跳动公司福利 1366人发布
查看5道真题和解析