3693. 爬樓梯II

思路

想要跳到第i格，只能從i - 1、i - 2、i - 3 跳過來，所以跳到這一格的最佳方法，
就是這三種情況選最好的。
用dp[i]代表跳到第i格的最佳方法，轉移方程如下。

dp[i] = cost[i] + min(dp[i - 1] + 1, dp[i - 2] + 4, dp[i - 3] + 9)

由於題目的下標差1，在數組的開頭加入 0 方便理解程式碼。 因為dp[i]只會考慮到自己的前三項，可以用來優化空間。

程式碼

1. 動態規劃

class Solution {
public:
    int climbStairs(int n, vector<int>& costs) {
        vector<int> f(n + 1, 0);
        costs.insert(costs.begin(), 0);
        for(int i = 1; i <= n; ++i) {
            f[i] = costs[i] + f[i - 1] + 1;
            if(i - 2 >= 0) f[i] = min(f[i], costs[i] + f[i - 2] + 4);
            if(i - 3 >= 0) f[i] = min(f[i], costs[i] + f[i - 3] + 9);
        }
        return f[n];
    }
};

2. 空間壓縮

class Solution {
public:
    int climbStairs(int n, vector<int>& costs) {
        int f0, f1, f2;
        f0 = f1 = f2 = 0;
        for(int i = 0; i < n; ++i) {
            int current = costs[i] + min({f0 + 9, f1 + 4, f2 + 1});
            f0 = f1;
            f1 = f2;
            f2 = current;
        }
        return f2;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$，可壓縮至$O(1)$