题解 | 爬楼梯II

题干分析

题设给定一个花费数组，已知我们可以上1/2/3级台阶，每次上到台阶i要花费costs[i]，同时根据上的台阶级数，追加花费1/4/9的花费。求从台阶0开始上到台阶n的最小花费为多少。

算法思路

拆分问题：

到达台阶n我们只能从台阶n-1/n-2/n-3开始分别花费对于的启动花费并追加移动花费到达台阶n。由此，我们设计dp[i]记录到达第i节台阶的最小花费，不难得到状态转移方程：

同时有初始条件：

同时我们注意到整个DP过程只涉及连续的四个状态值，因此可以进一步优化为常数额外空间消耗的迭代形式。

实现代码

• 递归与未进行内存优化的写法已注释

class Solution {
    /*
    vector<int> dp;

    int DP(int n, vector<int> &cost) {
        if (dp[n] != -1) return dp[n];
        int a1 = DP(n - 1, cost) + cost[n - 1] + 1;
        int a2 = DP(n - 2, cost) + cost[n - 1] + 4;
        int a3 = DP(n - 3, cost) + cost[n - 1] + 9;
        dp[n] = min(min(a1, a2), a3);
        return dp[n];
    }
public:
    int climbStairs(int n, vector<int>& costs) {
        dp.resize(n + 1, -1);
        dp[0] = 0;
        dp[1] = costs[0] + 1;
        if (n > 1) dp[2] = min(dp[1] + costs[1] + 1, costs[1] + 4);
        if (n < 3) return dp[n];
        return DP(n, costs);
    }*/
public:
    int climbStairs(int n, vector<int>& costs) {
        int a3 = 0, a2 = 0, a1 = 0; // ai分别表示距离目标需要跳i级台阶
        for (int c : costs) {
            int new_ = min(min(a3 + 9, a2 + 4), a1 + 1) + c;
            a3 = a2;
            a2 = a1;
            a1 = new_;
        }
        return a1;
    }
};

复杂度分析

• 时间复杂度：每个台阶迭代计算一次，时间复杂度为
• 空间复杂度：常数额外空间消耗，空间复杂度为