213. House Robber II

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Array、Dynamic Programming

一、題目

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

  • Input: nums = [2,3,2]
  • Output: 3
  • Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

  • Input: nums = [1,2,3,1]
  • Output: 4
  • Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
    Total amount you can rob = 1 + 3 = 4.

Example 3:

  • Input: nums = [1,2,3]
  • Output: 3

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

二、分析

  • 時間序列型的動態規劃問題。
    • 定義 dp[i][j]：第 i 間房子，j == 0 代表不搶，j == 1 代表搶。
    • 第 i 間房若搶，則前一間房必定不能搶；第 i 間房若不搶，前一間房可搶可不搶：
      • dp[i][0] = max(dp[i-1][1], dp[i-1][0])
      • dp[i][1] = dp[i-1][0] + val[i]
    • 最終的結果是 max(dp[n-1][0], dp[n-1][1])。
  • 多了一個條件是，房子的首尾相連。所以額外增加的條件多了一個限制為：
    • 第一間若搶了，則最後一間必不能搶。
    • 第一間若沒搶，則最後一間可搶可不搶。
    • 故相當於比較 第1間到第n-1間的最大值或第2間到第n間的最大值。
      • max(rob(nums, 0, n-1), rob(nums, 1, n))

三、解題

1. Dynamic Programming

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(n)\)
int rob(vector<int>& nums, int lo, int hi) {
    vector<vector<int>> dp(hi, vector<int>(2, 0));
    dp[lo][1] = nums[lo];
    for (int i = lo+1; i < hi; i++) {
        dp[i][0] = max(dp[i-1][1], dp[i-1][0]);
        dp[i][1] = dp[i-1][0] + nums[i];
    }
    return max(dp[hi-1][0], dp[hi-1][1]);
}
int rob(vector<int>& nums) {
    int n = nums.size();
    if (n <= 3) return *max_element(nums.begin(), nums.end());
    return max(rob(nums, 0, n-1), rob(nums, 1, n));
}

2. Dynamic Programming(SC optimized)

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(1)\)
int rob(vector<int>& nums, int lo, int hi) {
    int robbed = nums[lo];
    int passed = 0;
    for (int i = lo+1; i < hi; i++) {
        int tmp = robbed;
        robbed = passed + nums[i];
        passed = max(tmp, passed);
    }
    return max(robbed, passed);
}
int rob(vector<int>& nums) {
    int n = nums.size();
    if (n <= 3) return *max_element(nums.begin(), nums.end());
    return max(rob(nums, 0, n-1), rob(nums, 1, n));
}

回目錄 Catalog