[LeetCode] 198. House Robber 打家劫舍

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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [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: [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.

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Also thanks to @ts for adding additional test cases.

這道題的本質(zhì)相當(dāng)于在一列數(shù)組中取出一個(gè)或多個(gè)不相鄰數(shù)，使其和最大。那么對(duì)于這類求極值的問題首先考慮動(dòng)態(tài)規(guī)劃 Dynamic Programming 來解，維護(hù)一個(gè)一位數(shù)組 dp，其中 dp[i] 表示 [0, i] 區(qū)間可以搶奪的最大值，對(duì)當(dāng)前i來說，有搶和不搶兩種互斥的選擇，不搶即為 dp[i-1]（等價(jià)于去掉 nums[i] 只搶 [0, i-1] 區(qū)間最大值），搶即為 dp[i-2] + nums[i]（等價(jià)于去掉 nums[i-1]）。再舉一個(gè)簡單的例子來說明一下吧，比如說 nums為{3, 2, 1, 5}，那么來看 dp 數(shù)組應(yīng)該是什么樣的，首先 dp[0]=3 沒啥疑問，再看 dp[1] 是多少呢，由于3比2大，所以搶第一個(gè)房子的3，當(dāng)前房子的2不搶，則dp[1]=3，那么再來看 dp[2]，由于不能搶相鄰的，所以可以用再前面的一個(gè)的 dp 值加上當(dāng)前的房間值，和當(dāng)前房間的前面一個(gè) dp 值比較，取較大值當(dāng)做當(dāng)前 dp 值，這樣就可以得到狀態(tài)轉(zhuǎn)移方程 dp[i] = max(num[i] + dp[i - 2], dp[i - 1]), 且需要初始化 dp[0] 和 dp[1]，其中 dp[0] 即為 num[0]，dp[1] 此時(shí)應(yīng)該為 max(num[0], num[1])，代碼如下：

解法一：

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

還有一種解法，核心思想還是用 DP，分別維護(hù)兩個(gè)變量 robEven 和 robOdd，顧名思義，robEven 就是要搶偶數(shù)位置的房子，robOdd 就是要搶奇數(shù)位置的房子。所以在遍歷房子數(shù)組時(shí)，如果是偶數(shù)位置，那么 robEven 就要加上當(dāng)前數(shù)字，然后和 robOdd 比較，取較大的來更新 robEven。這里就看出來了，robEven 組成的值并不是只由偶數(shù)位置的數(shù)字，只是當(dāng)前要搶偶數(shù)位置而已。同理，當(dāng)奇數(shù)位置時(shí)，robOdd 加上當(dāng)前數(shù)字和 robEven 比較，取較大值來更新 robOdd，這種按奇偶分別來更新的方法，可以保證組成最大和的數(shù)字不相鄰，最后別忘了在 robEven 和 robOdd 種取較大值返回，代碼如下：

解法二：

class Solution {
public:
    int rob(vector<int>& nums) {
        int robEven = 0, robOdd = 0, n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) {
                robEven = max(robEven + nums[i], robOdd);
            } else {
                robOdd = max(robEven, robOdd + nums[i]);
            }
        }
        return max(robEven, robOdd);
    }
};

上述方法還可以進(jìn)一步簡潔，我們使用兩個(gè)變量 rob 和 notRob，其中 rob 表示搶當(dāng)前的房子，notRob 表示不搶當(dāng)前的房子，那么在遍歷的過程中，先用兩個(gè)變量 preRob 和 preNotRob 來分別記錄更新之前的值，由于 rob 是要搶當(dāng)前的房子，那么前一個(gè)房子一定不能搶，所以使用 preNotRob 加上當(dāng)前的數(shù)字賦給 rob，然后 notRob 表示不能搶當(dāng)前的房子，那么之前的房子就可以搶也可以不搶，所以將 preRob 和 preNotRob 中的較大值賦給 notRob，參見代碼如下：

解法三：

class Solution {
public:
    int rob(vector<int>& nums) {
        int rob = 0, notRob = 0, n = nums.size();
        for (int i = 0; i < n; ++i) {
            int preRob = rob, preNotRob = notRob;
            rob = preNotRob + nums[i];
            notRob = max(preRob, preNotRob);
        }
        return max(rob, notRob);
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/198

參考資料：

https://leetcode.com/problems/house-robber/description/

https://leetcode.com/problems/house-robber/discuss/55681/java-on-solution-space-o1

https://leetcode.com/problems/house-robber/discuss/55693/c-1ms-o1space-very-simple-solution

https://leetcode.com/problems/house-robber/discuss/55695/java-dp-solution-on-runtime-and-o1-space-with-inline-comment

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(198.打家劫舍)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)打家劫舍內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論