LeetCode演算法題-House Robber（Java實現）
這是悅樂書的第187 次更新，第189 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第46題（順位題號是198）。你是一個專業的強盜，計劃在街上搶劫房屋。 每個房子都藏著一定數量的錢，阻止你搶劫他們的唯一限制因素是相鄰的房屋有連線的安全系統，如果兩個相鄰的房子在同一個晚上被闖入，它將自動聯絡警方。給出一個代表每個房子的金額的非負整數列表，確定今晚可以搶劫的最大金額而不警告警察。例如：
輸入：[1,2,3,1]
輸出：4
說明：Rob house 1（money = 1）然後搶房子3（錢= 3）。您可以搶奪的總金額= 1 + 3 = 4。
輸入：[2,7,9,3,1]
輸出：12
說明：Rob house 1（money = 2），rob house 3（money = 9）和rob house 5（money = 1）。您可以搶奪的總金額= 2 + 9 + 1 = 12。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
初始思路是偶數、奇數下標的元素分別求和，然後判斷其中的最大值，但是有個問題，此思路只考慮了隔一個元素，那要是隔兩個、三個甚至更多呢？在每次算完奇數或者偶數下標元素之和之後，還要和已有的偶數下標元素和或者奇數下標元素和做最大值判斷，最後再取偶數下標元素和、奇數下標元素和中的最大值。
特殊情況：當陣列為null或者陣列中沒有任何元素時，直接返回0。
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int sum = 0;
int sum2 = 0;
for(int i=0; i<nums.length; i++){
if (i%2 == 0) {
sum = Math.max(sum+nums[i], sum2);
} else {
sum2 = Math.max(sum2+nums[i], sum);
}
}
return Math.max(sum, sum2);
}
此解法的時間複雜度是O(n)，空間複雜度是O(1)。
03 第二種解法
使用動態規劃演算法。
第一步，我們找到此問題的遞迴關係，強盜有兩種選擇：
a）搶劫當前的房子i
b）不搶劫當前的房子i
如果選擇選項“a”，則意味著無法搶奪之前的i-1房屋，但可以安全地前往前一個i-2之前的房屋並獲得隨後的所有累積戰利品。
如果選擇了一個選項“b”，強盜將從搶劫i-1和剩下所有建築物中獲得所有可能的戰利品。
因此，利益最大的結果就有兩種可能：
1）搶劫當前房屋 + 前一次房屋搶劫
2）從之前的房屋搶劫和之前捕獲的任何戰利品中掠奪
對此，可以得出以下公式：
rob(i) = Math.max( rob(i-2) + currentHouseValue, rob(i-1) )
第二步，在分析出了遞迴關係後，我們可以得到自頂向下的遞迴解法，對此，我們可以寫出第一版的程式碼：
public int rob(int[] nums) {
return rob(nums, nums.length-1);
}
private int rob(int[] nums, int i) {
if (i < 0) {
return 0;
}
return Math.max(rob(nums, i-2) + nums[i], rob(nums, i-1));
}
第三步，上面的遞迴演算法，會造成大量的重複計算，對此可以使用備忘錄演算法來記錄前一步的值，同樣是使用自頂向下的遞迴演算法。
public int rob(int[] nums) {
int[] memo = new int[nums.length + 1];
Arrays.fill(memo, -1);
return rob(nums, nums.length - 1);
}
private int rob(int[] nums, int i) {
if (i < 0) {
return 0;
}
if (memo[i] >= 0) {
return memo[i];
}
int result = Math.max(rob(nums, i-2) + nums[i], rob(nums, i-1));
memo[i] = result;
return result;
}
Arrays.fill(memo, -1)方法表示memo陣列的元素全部由-1來填充。
第四步，備忘錄演算法不變，可以將遞迴演算法用迭代替代，變成自底向上的方式。
public int rob(int[] nums) {
if (nums.length == 0) return 0;
int[] memo = new int[nums.length + 1];
memo[0] = 0;
memo[1] = nums[0];
for (int i = 1; i < nums.length; i++) {
int val = nums[i];
memo[i+1] = Math.max(memo[i], memo[i-1] + val);
}
return memo[nums.length];
}
第五步，可以注意到，在上一步中我們只使用memo[i]和memo[i-1]，所以只需要兩步。我們可以將它們儲存在2個變數中，而不必使用備忘錄演算法。
public int rob(int[] nums) {
if (nums.length == 0) return 0;
int prev1 = 0;
int prev2 = 0;
for (int num : nums) {
int tmp = prev1;
prev1 = Math.max(prev2 + num, prev1);
prev2 = tmp;
}
return prev1;
}
上述解法的思路參考至ofollow,noindex">@heroes3001 的說明，寫的很好，就按照自己的理解翻譯了下，按照這五個步驟基本可以解決類似的動態規劃演算法問題。最下方的原文連結就是該作者原答案。
04 小結
演算法專題目前已連續日更超過一個月，演算法題文章46 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！