一.LeetCode198.打家劫舍
1.題目鏈接
https://leetcode-cn.com/problems/house-robber/
2.題目
你是一個(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)裝置的情況下，能夠偷竊到的最高金額蔓腐。
3.舉例
示例1
輸入: [1,2,3,1]
輸出: 4
解釋: 偷竊 1 號(hào)房屋 (金額 = 1) ，然后偷竊 3 號(hào)房屋 (金額 = 3)逗鸣。
偷竊到的最高金額 = 1 + 3 = 4 合住。
示例2
輸入: [2,7,9,3,1]
輸出: 12
解釋: 偷竊 1 號(hào)房屋 (金額 = 2), 偷竊 3 號(hào)房屋 (金額 = 9)，接著偷竊 5 號(hào)房屋 (金額 = 1)撒璧。
偷竊到的最高金額 = 2 + 9 + 1 = 12 透葛。
4.解題思路
1.顯然要采用動(dòng)態(tài)規(guī)劃法，假設(shè)從最后一家店鋪開(kāi)始搶卿樱，那么只會(huì)遇到2種情況僚害，即：搶這家店和下下家店，或者不搶這家店，即dp[n]=max{dp[n-1],dp[n-2]+arr[n]}萨蚕。
2.如果采用暴力的算法靶草，我們來(lái)分析一下：
如果我們開(kāi)始搶的是第n-1家店，那么后面可以是（n-3,n-4,n-5,n-6....）;
如果我們開(kāi)始搶的是第n-2家店岳遥，那么后面可以是（n-4,n-5,n-6,....）;
那么這兩種情況顯然n-3之后的n-4,n-5,n-6,....都重復(fù)計(jì)算了奕翔。顯然這里有非常大的優(yōu)化空間,通常我們使用空間來(lái)?yè)Q時(shí)間，即用一個(gè)result數(shù)組記錄每次計(jì)算的結(jié)果浩蓉，這樣每次情況只需要計(jì)算一次派继，再次遇到只需直接返回結(jié)果即可，大大優(yōu)化了時(shí)間捻艳。
5.代碼實(shí)現(xiàn)
public class HouseRobber {
public int[] result;
public int rob1(int[] arr){
result = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
result[i] = -1;
}
return solve(arr, arr.length - 1);
}
public int solve(int[] arr, int index){
if (index < 0){
return 0;
}
if (result[index] > 0){
return result[index];
}
result[index] = Math.max(solve(arr, index - 1), solve(arr, index - 2) + arr[index]);
return result[index];
}
}
二.LeetCode213.打家劫舍II
1.題目鏈接
https://leetcode-cn.com/problems/house-robber-ii/
2.題目
你是一個(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)裝置的情況下，能夠偷竊到的最高金額霍掺。
3.舉例
示例1
輸入: [2,3,2]
輸出: 3
解釋: 你不能先偷竊 1 號(hào)房屋（金額 = 2）匾荆，然后偷竊 3 號(hào)房屋（金額 = 2）, 因?yàn)樗麄兪窍噜彽摹?示例2
輸入: [1,2,3,1]
輸出: 4
解釋: 你可以先偷竊 1 號(hào)房屋（金額 = 1），然后偷竊 3 號(hào)房屋（金額 = 3）杆烁。
偷竊到的最高金額 = 1 + 3 = 4 牙丽。
4.解題思路
1.打家劫舍II跟LeetCode198.打家劫舍不同的地方在于，第一個(gè)房屋和最后一個(gè)房屋是相鄰的兔魂，那么第一個(gè)房屋和最后一個(gè)房屋不能同時(shí)打劫烤芦，也就是說(shuō)要么從第一家開(kāi)始劫到倒數(shù)第二家，要么從第二家開(kāi)始劫到最后一家析校，分別算出這兩種情況下的最大搶劫金額构罗，然后取更大的就行。
2.從第一家開(kāi)始劫到倒數(shù)第二家智玻，那么從倒數(shù)第二家開(kāi)始往前面劫即可遂唧。從第二家開(kāi)始劫到最后一家這種情況，第一家房屋不太好處理吊奢，那直接把result[0]設(shè)為0盖彭，劫到第一家的時(shí)候直接返回result[0]，也就相當(dāng)于沒(méi)有劫第一家。
5.代碼實(shí)現(xiàn)
public class HouseRobber {
public int[] result;
public int rob2(int[] arr){
result = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
result[i] = -1;
}
int result1 = solve1(arr, arr.length - 2);
for (int i = 0; i < arr.length; i++) {
result[i] = -1;
}
result[0] = 0;
int result2 = solve2(arr, arr.length - 1);
return result1 >= result2 ? result1 : result2;
}
public int solve1(int[] arr, int index){
if (index < 0){
return 0;
}
if (result[index] > 0){
return result[index];
}
result[index] = Math.max(solve1(arr, index - 1), solve1(arr, index - 2) + arr[index]);
return result[index];
}
public int solve2(int[] arr, int index){
if (index < 0){
return 0;
}
if (result[index] >= 0){
return result[index];
}
result[index] = Math.max(solve2(arr, index -1), solve2(arr, index - 2) + arr[index]);
return result[index];
}
}
