LeetCode 198. House Robber [Medium] [C++] 解題筆記

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems 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 = [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 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

想法:

    這題是經典的 dp 題，假設 dp[i] 表示到從 1 ~ i 間房子中能搶到的最大金額，則 dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1])

，因為不能連續搶相鄰的兩間房子所以到當前這間房子為止最多可搶的金額會是搶到前一間為止(搶了前一間，不能搶連續的兩間，因此搶了前一間就不能再搶

當前這間)和 搶了當前這間加上搶到前兩間為止 這兩者之間的最大值。

完整程式碼:

解法一:

/* dp solution */

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) { return 0; }
        if (nums.size() == 1) { return nums.at(0); }
        vector<int> dp(nums.size(), 0);
        dp.at(0) = nums.at(0);
        dp.at(1) = max(nums.at(0), nums.at(1));
        for (int i = 2; i < nums.size(); i++) {
            dp.at(i) = max(dp.at(i-1), dp.at(i-2) + nums.at(i));
        }
        
        return dp.at(nums.size()-1);
    }
};

解法二:

/* with O(1) space */
class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) { return 0; }
        if (nums.size() == 1) { return nums.at(0); }
        int pprev = nums.at(0);
        int prev = max(nums.at(0), nums.at(1));
        int cur = prev;
        for (int i = 2; i < nums.size(); i++) {
            cur = max(prev, pprev + nums.at(i));
            pprev = prev;
            prev = cur;
        }
        
        return cur;
    }
};