題目網址：https://leetcode.cn/problems/min-cost-climbing-stairs/

題意：給一整數 array cost, 其中 cost[i] 代表從第 i 皆樓梯往上爬所需支付的費用。一旦支付該費用, 可以選擇往上爬一個 or 二個台階。

可以選擇從 index 為 0 or 1 的位置開始往上爬。

請計算到達樓梯頂部 index = cost.size() 所需的最小費用。

Solution 1：

想法：利用 DP, 定義 dp[i] 為抵達 index = i 所需的最小費用, 因此 dp[i] 為 抵達前一階的最小費用 + 該階的費用、抵達前兩階的最小費用 + 該階的費用 中取較小者

  • dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        const int n = cost.size();
        vector<int> dp(n + 1, 0);
        for (int i = 2; i <= n; ++i) { // index = 0 和 1 的費用都為 0
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp.back();
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(n)$ ➔ dp

Solution 2：

想法：改進 Solution 1, 因為發現計算 dp[i] 只需用到 dp[i - 1]、dp[i - 2] 即可, 也就是說只需紀錄 dp[i - 1] 和 dp[i - 2] 就好, 根本不需要開到 n 個空間

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int one = 0; // dp[i - 1]
        int two = 0; // dp[i - 2]

        for (int i = 2; i <= cost.size(); ++i) {
            int cur = min(one + cost[i - 1], two + cost[i - 2]);
            two = one;
            one = cur;
        }

        return one;
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(1)$ ➔ 只需常數空間