Leetcode----213打家劫舍||+198打家劫舍|

今天的每日一題是《打家劫舍||》，先找到《打家劫舍|》做一下，熟悉一下題目。

打家劫舍|

解題思路

簡單的動态規劃問題，找到規律就非常簡單，但是題目的範圍給挖了一個坑，需要注意規避（數組的長度是從0開始的，是以要對數組長度為0的情況進行處理，雖然我沒嘗試不處理會怎麼樣，但是也應該注意到這個問題）。

1. 因為不能偷連續的兩個房子的财物，是以對于數組長度length=1和2的情況進行處理，分别傳回nums[0]和nums[0]、nums[1]中的較大值；
2. 對于length>2的情況，設定dp[0]和dp[1]分别等于nums[0]和nums[1]，下面開始進行動态規劃；因為為了取得更多的錢，在不觸發警報（不偷連續兩家）的前提下，每次應該偷錢最多的家庭，是以每次應該加上除了鄰近的上一戶之外，累計金額最高的幾戶家庭，是以使用max存儲目前累計金額的最大值，每戶自己的錢和max進行相加，即是目前最大的累計金額；
3. 因為max是目前家庭i之前的i-2戶的累計金額的最大值，是以在輸出結果時，需要比較max（即前i-2戶的累計最大值）、dp[length-2]（前i-1戶的累計最大值）、dp[length-1]（前i戶的累計最大值）中的最大值，即為能偷到錢的最大累計值。

代碼

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if(length == 0)
            return 0;
        if(length == 1)
            return nums[0];
        if(length == 2)
        {
            return nums[0]> nums[1]?nums[0]:nums[1];
        }
        int dp[] = new int[length];
        dp[0] = nums[0];
        dp[1] = nums[1];
        int max = dp[0];

        for(int i=2;i<length;i++)
        {            
            max = Math.max(max, dp[i-2]);
            dp[i] = nums[i] + max;
        }
        return Math.max(Math.max(max, dp[length-2]), dp[length-1]);
    }
}
           

打家劫舍||

解題思路

emmmmm，思考問題還是不嚴謹，期間出了很多小的問題，第三次送出才通過。。。

與198打家劫舍|的問題相比，該題添加了一個環形排列的新特點，是以選擇哪個點作為動态規劃的起始點顯得至關重要，是以我沒選。。。哈哈哈。直接全部做一次起始點，找到其中的最大結果就可以了。

1. 對于數組長度為1和2的情況進行單獨處理；
2. 使數組的每個節點都作為起始節點，然後分别進行動态規劃，因為最後一個節點的值與第一個節點有關，但是因為本方法是循環處理的，是以直接不用對每次的最後一個節點進行處理；
3. 在每次動态規劃後，記錄本次的最大值cur_max，與max進行對比，存儲較大的值到max中，最後傳回max即可。

具體的詳見代碼中注釋

代碼

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if(length == 1)
            return nums[0];
        if(length == 2)
        {
            return nums[0]> nums[1]?nums[0]:nums[1];
        }

        int max,cur_max,i;
        int count = 0;
        max=-1;

        while(count<length)
        {
            i=count;
            int dp[] = new int[length];
            dp[0] = nums[i];
            i = (i+1)%length;
            dp[1] = nums[i];

            cur_max = dp[0];
            i = (i+1)%length;
            int j=2;//之是以設定j是因為無論數組内容如何循環處理，dp的索引值始終是一緻的，最開始沒注意這一點，而是直接利用i的值，錯了很久。。。
            while(i!=(count-1+length)%length)
            {
                cur_max = Math.max(cur_max, dp[j-2]);//因為不能偷鄰近的兩家，是以cur_max存儲的是前j-2家的累計最大值
                dp[j] = nums[i] + cur_max;
                i = (i+1)%length;//因為是循環處理，是以要加上length并進行取餘
                j++;
            }

            cur_max = Math.max(cur_max, dp[length-2]);//因為不用管最後一個節點，是以與198打家劫舍|的代碼Math.max(Math.max(max, dp[length-2]), dp[length-1])不同
            max = Math.max(max,cur_max);//儲存每次循環的最大值

            count++;
        }
        return max;
    }
}