輸入：一個數組nums，每一個元素nums[i]表示第i個房間的價值。
輸出：一個搶劫犯能搶到又不會被警察發現的最大價值。
規則：如果搶劫犯搶了相鄰房間，那么報警裝置就會觸發，警察會得到通知。
分析：我可以從第0個房間開始，可能搶，也可能不搶，一直到最后一個房間，得到的價值取最大值就是結果。用回溯法吧。

public class HouseRobber198 {private int[] nums;private int max = 0;public int rob(int[] nums) {this.nums = nums;max = 0;rob(0,0,true);return max;}private void rob(int idx,int value,boolean robable){if(idx==nums.length){max = Math.max(max,value);}else{//System.out.println(idx+" "+robbed+" "+value);int idx2 = robable?1:0;if(robable){rob(idx+1,value+nums[idx],false);}rob(idx+1,value,true);}} }

分析2：這樣寫完，畫決策分析樹，或者打印idx，robbed，value，就會發現有些是重復的。2 false 重復了兩次。因為要計算的是最大價值，所以只需要保留一個最大值。所以我們可以使用緩存減少計算量。

0 false 0 1 true 1 2 false 1 3 true 4 3 false 1 1 false 0 2 true 2 3 false 2 2 false 0 3 true 3 3 false 0 private int[] nums;private int max = 0;private int[][] memo;public int rob(int[] nums) {this.nums = nums;max = 0;memo = new int[nums.length][2];rob(0,0,true);return max;}private void rob(int idx,int value,boolean robable){if(idx==nums.length){max = Math.max(max,value);}else{//System.out.println(idx+" "+robbed+" "+value);int idx2 = robable?1:0;if(value<memo[idx][idx2]){return;}memo[idx][idx2]=value;if(robable){rob(idx+1,value+nums[idx],false);}rob(idx+1,value,true);}}

分析3：把以上代碼改為迭代版本。把變量名memo改為dp。

public int rob(int[] nums) {if(nums==null || nums.length==0) return 0;int n = nums.length;int[][] dp = new int[n][2];dp[0][0] = 0;dp[0][1] = nums[0];for(int i=1;i<n;i++){dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]);dp[i][1] = dp[i-1][0]+nums[i];}return Math.max(dp[n-1][0],dp[n-1][1]);}

看著寫出來的dp代碼我發現可以這樣整理自己的邏輯。

給定一個數組nums={1,2,3,1}。
如果只有第0個房間，可能搶也可能不搶。但這基本是廢話，不搶顯然拿不到價值。
　　搶，得1，
　　不搶得0。
　　取最大值，得到的價值是1。
如果只有第0個和第1個 房間。對于房間1可能搶，也可能不搶。
　　如果搶第1個房間，那得到的價值是2，因為第0個房間不搶的價值是0。
　　如果不搶第1個房間，那得到的價值是1，因為第0個房間搶，得1，不搶得0，取最大值。Max(搶第1個房間，不搶第1個房間)=2。

如果只有第0個、第1個 ，第2個房間。對于房間2可能搶，也可能不搶。
　　如果不搶第2個房間，那最后拿到的價值就是Max(搶第1個房間，不搶第1個房間)=2。
　　如果搶第2個房間，那最后拿到的價值就是不搶第1個房間的價值+nums[2]=1+3=4。
　　那最大的答案是Max(不搶第2個房間,搶第2個房間)=4。
分析到這里我們知道在新增一個房間的時候與上一個房間的搶和不搶獲得的價值有關系。最后答案是在當前房間號搶和不搶狀態取最大值。這樣基本上dp方程就出來了。

我們用dp[i]記錄第i個房間的狀態，dp[i][0]表示第i個房間不搶的價值，dp[i][1]代表第i個房間搶后的價值。 dp[i][0]=max(dp[i-1][0],dp[i-1][1]) dp[i][1]=dp[i-1][0]+nums[i]

嗯，這就是我的思考方式，是從回溯算法開始，不斷優化，最后整理到dp，然后總結出dp應該這樣思考。當然還缺少一步是內存優化。只與上一步的狀態有關系，可以用變量表示，而無需數組。

public int robV4(int[] nums) {if(nums==null || nums.length==0) return 0;int n = nums.length;int v0 = 0 ,v1=nums[0];for(int i=1;i<n;i++){int tmp0 = Math.max(v0,v1);int tmp1 = v0+nums[i];v0=tmp0;v1=tmp1;}return Math.max(v0,v1);}

213 House Robber II

class Solution {public int rob(int[] nums) {if(nums==null || nums.length==0) return 0;if(nums.length==1) return nums[0];return Math.max(rob(nums,0,nums.length-2),rob(nums,1,nums.length-1));}public int rob(int[] nums,int start,int end) {int n = nums.length;int[][] dp = new int[2][n];dp[0][start] = nums[start];dp[1][start] = 0;for(int i=start+1;i<=end;i++){dp[0][i] = dp[1][i-1] + nums[i];dp[1][i] = Math.max(dp[0][i-1],dp[1][i-1]);}return Math.max(dp[0][end],dp[1][end]);} }

總結

以上是生活随笔為你收集整理的[dp]leetcode 198. House Robber的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。