目錄

打家劫舍Ⅰ

題目分析?

代碼一?

代碼二

打家劫舍Ⅱ

---

?

?

打家劫舍Ⅰ

你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋。每間房?jī)?nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警。

給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你 不觸動(dòng)警報(bào)裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。

?

輸入：[2,7,9,3,1]
輸出：12
解釋：偷竊 1 號(hào)房屋 (金額 = 2), 偷竊 3 號(hào)房屋 (金額 = 9)，接著偷竊 5 號(hào)房屋 (金額 = 1)。
?? ? 偷竊到的最高金額 = 2 + 9 + 1 = 12 。

題目分析?

nums	2	7	9	3	1
R	2	7+0	9+2	3+7	1+11
NR	0	2	7	11	11

?R數(shù)組代表偷，NR代表不偷，不偷的話就考慮從上次偷與不偷的抉擇中選擇最大金額，最終返回較大值。

for(int i=1;i<n;i++){
? ? ? ? R[i]=nums[i]+NR[i-1];
? ? ? ? NR[i]=Math.max(R[i-1],NR[i-1]);
?}
?return Math.max(R[n-1],NR[n-1]);

代碼一?

class Solution {public int rob(int[] nums) {int n=nums.length;if(n==0) return 0;//狀態(tài)容器int[] R = new int [n];//代表偷int[] NR= new int [n];//代表不偷//初始化R[0]=nums[0];NR[0]=0;//狀態(tài)轉(zhuǎn)移方程for(int i=1;i<n;i++){R[i]=nums[i]+NR[i-1];NR[i]=Math.max(R[i-1],NR[i-1]);}return Math.max(R[n-1],NR[n-1]);}
}

空間優(yōu)化

class Solution {public int rob(int[] nums) {int n=nums.length;if(n==0) return 0;//狀態(tài)容器int R=0;int NR=0;//狀態(tài)轉(zhuǎn)移方程for(int i=0;i<n;i++){int max=Math.max(R,NR);R=nums[i]+NR;NR=max;}return Math.max(R,NR);}
}

?

代碼二

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

打家劫舍Ⅱ

?

你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋，每間房?jī)?nèi)都藏有一定的現(xiàn)金。這個(gè)地方所有的房屋都 圍成一圈 ，這意味著第一個(gè)房屋和最后一個(gè)房屋是緊挨著的。同時(shí)，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警 。

給定一個(gè)代表每個(gè)房屋存放金額的非負(fù)整數(shù)數(shù)組，計(jì)算你 在不觸動(dòng)警報(bào)裝置的情況下 ，今晚能夠偷竊到的最高金額。

?

示例?1：

輸入：nums = [2,3,2]
輸出：3
解釋：你不能先偷竊 1 號(hào)房屋（金額 = 2），然后偷竊 3 號(hào)房屋（金額 = 2）, 因?yàn)樗麄兪窍噜彽摹?/strong>

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/house-robber-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

?

//本題可以拆成兩個(gè)198來看，也是震驚了，一次次打破認(rèn)知class Solution {public int rob(int[] nums) {int n=nums.length;//最后考慮到邊界條件if(n==0) return 0;if(n==1) return nums[0];if(n==2) return Math.max(nums[0],nums[1]);//不過只有兩間房的時(shí)候....感覺真有些問題int r2=robprocess(nums,0,n-2);int r1=robprocess(nums,1,n-1);return Math.max(r1,r2);}public int robprocess(int[] nums,int start,int end){int n=nums.length;if(n==0) return 0;//狀態(tài)容器int R=0;int NR=0;//狀態(tài)轉(zhuǎn)移方程for(int i=start;i<=end;i++){int max=Math.max(R,NR);R=nums[i]+NR;NR=max;}return Math.max(R,NR);}
}

?

?