LeetCode—House Robber 尋找數組不相鄰組合最大值DP

LeetCode—House Robber 尋找數組不相鄰組合最大值DP

題目設計了一個搶劫犯的情景，其實就是求數組中不相鄰數據進行組合得到的最大值

舉一個例子

假設數據： 8 3 6 15 4 9 7 10

那麼首先可能選取 8 ， 3

每一個數字的選取都是根據他的前兩個數字，前三個數字得到的最大值進行選擇，等到6的時候考慮前面只能和8組合 8，3,14

到數字15，那麼就可以考慮在8,3中進行組合 8,3,14,23,4,9,7,10

接下來的步驟：

8,3,14,23,18,9,7,10

8,3,14,23,18,32,7,10

8,3,14,23,18,32,30,10

8,3,14,23,18,32,30,42 最後是42

class Solution {
public:
    int rob(vector &num) {
        if(num.empty())
        {
            return 0;
        }
        int res = 0;
        int length = num.size();
        if(1 == length)
        {
            return num[0];
        }
        if(length >= 3)
        {
            num[2] = num[0]+num[2];
        }
        for(int i = 3; i < length; i++)
        {
            if(num[i-2]>num[i-3])
            {
                num[i] += num[i-2];
            }
            else
            {
                num[i] += num[i-3];
            }
            
        }
        return (num[length-2]>num[length-1])? num[length-2]:num[length-1];
        
    }
};

A[i][0]表示第i次沒有搶劫，A[i][1]表示第i次進行了搶劫

即A[i+1][0] = max(A[i][0], A[i][1]).. 那麼rob當前的house，只能等於上次沒有rob的+money[i+1], 則A[i+1][1] = A[i][0]+money[i+1].

實際上只需要兩個變量保存結果就可以了，不需要用二維數組

1. class Solution {
2. public:
3. int rob(vector &num) {
4. int best0 = 0; // 表示沒有選擇當前houses
5. int best1 = 0; // 表示選擇了當前houses
6. for(int i = 0; i < num.size(); i++){
7. int temp = best0;
8. best0 = max(best0, best1); // 沒有選擇當前houses，那麼它等於上次選擇了或沒選擇的最大值
9. best1 = temp + num[i]; // 選擇了當前houses，值只能等於上次沒選擇的+當前houses的money
10. }
11. return max(best0, best1);
12. }
13. };