題目網址：https://leetcode.cn/problems/house-robber/

題意：你是一名專業的強盜, 計劃搶劫沿路的房子。每棟房子都藏有一定數量的金錢, 唯一阻止你搶劫的限制是相鄰的房子都連接了安全系統, 如果闖入兩棟相鄰的房子，它會自動報警。

給一整數 array nums, 表示每棟房子所藏有的金額, 返回在不報警的情況下能搶劫的最大金額。

Solution 1：

想法：利用 DP, 其中 dp[i] 代表 index 位於區間 [0, i] 這 i + 1 間房子中可搶劫的最大金額。接著，我們考慮單一一間房子的情況，對於 index = i 的房子我們有兩種選擇，要搶 or 不搶

  • 若 index = i 的房子不搶, 此時的最大金額 = 區間 [0, i - 1] 的最大金額 = dp[i - 1]
  • 若 index = i 的房子要搶, 此時的最大金額 = 區間 [0, i - 2] 的最大金額 + index = i 的金額 = dp[i - 2] + nums[i]

➔ 因此 dp[i] 就為這兩種可能中取較大者, dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])

此外，由於我們的 index 是從 0 開始取的，因此要考慮 dp[i - 1]、dp[i - 2] 越界的情況, 根據 dp[i] 的定義, dp[-1] 代表在 nums 中的 index 區間 [0, -1] 可搶劫的最大金額，但 nums 中 index 區間 [0, -1] 中根本沒有任何數，所以可搶劫的最大金額可視為 0。所以一旦要存取的 index 越界我們就取 0。

class Solution {
public:
    int rob(vector<int>& nums) {
        const int n = nums.size();
        vector<int> dp(n, 0);

        for (int i = 0; i < n; ++i) {
            dp[i] = max((i > 0 ? dp[i - 1] : 0),
                        (i > 1 ? dp[i - 2] : 0) + nums[i]);
        }
        return dp.back();
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(n)$ ➔ dp

Solution 2：

想法：Solution 1 的改進, 計算 dp[i] 只需用到 dp[i - 1] 和 dp[i - 2], 不需要開到 n 個空間

class Solution {
public:
    int rob(vector<int>& nums) {
        int one = 0, two = 0; // two, one, [n1, n2, ...]
        for (const auto& num : nums) {
            int curMax = max(one, two + num);
            two = one;
            one = curMax;
        }
        return one;
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(1)$ ➔ 只需常數空間