力扣198——打家劫舍
- 2020 年 2 月 19 日
- 筆記
這次準備連講三道題，這道題就是最基礎的，利用動態規劃可以解決。
原題
你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。
給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，能夠偷竊到的最高金額。
示例 :
輸入: [1,2,3,1] 輸出: 4 解釋: 偷竊 1 號房屋 (金額 = 1) ，然後偷竊 3 號房屋 (金額 = 3)。 偷竊到的最高金額 = 1 + 3 = 4 。
原題url：https://leetcode-cn.com/problems/house-robber/
解題
動態規劃-自頂向下
動態規劃大家應該很容易就想到，如果偷了當前的金錢，下一家就不能偷，如果不偷當前的金錢，可以考慮下一家。比如：
小偷到了第3家，他有兩個選擇：不偷第3家之後去第4家、偷完第3家之後去第5家。這時他需要比較的是：
- 從第4家開始能偷到的最多金錢
- 第3家的金錢加上從第5家開始能偷到的最多金錢 上面兩者誰更多，就選擇怎麼做。
那主要目的就是要求出從當前到結尾可以偷到的最大值，為了不重複計算，可以利用一個數組記錄中間結果。
接下來看看代碼：
class Solution { public int rob(int[] nums) { if (nums.length == 0) { return 0; } // 存儲中間結果 int[] result = new int[nums.length]; Arrays.fill(result, -1); // 動態規劃，利用中間結果，尋找最大值 dp(0, nums, result); return result[0]; } public int dp(int start, int[] nums, int[] result) { if (start >= nums.length) { return 0; } if (result[start] != -1) { return result[start]; } result[start] = Math.max( // 選擇偷當前的家 nums[start] + dp(start + 2, nums, result), // 選擇不偷當前的家 dp(start + 1, nums, result) ); return result[start]; } }
提交OK。
動態規劃-自底向上
上面的寫法其實是從頭向尾考慮，寫法上是遞歸。那麼如果想不用遞歸呢？畢竟遞歸也是有缺陷的，如果次數過多，總調用棧就會很長。那我們來改造一下。
如果我們是從尾向頭考慮呢？也就是從最後一家開始，選擇偷或者不偷，最終到第一家。思想上還是很好理解的，和上面差不多，讓我們看看代碼：
class Solution { public int rob(int[] nums) { if (nums.length == 0) { return 0; } // 存儲中間結果 int[] result = new int[nums.length + 2]; // 動態規劃，利用中間結果，尋找最大值 for (int i = nums.length - 1; i >= 0; i--) { result[i] = Math.max( // 當前不偷 result[i + 1], // 當前偷 nums[i] + result[i + 2] ); } return result[0]; } }
提交也是OK的。
空間上的優化
我們仔細觀察一下上面的寫法，其實每次你利用到的中間狀態只有兩個，下一個位置和再下一個位置。那麼此時我們也可以用三個變量來存儲就夠了，兩個存儲之後的值，還有一個存儲當前的值。
讓我們來看看代碼：
class Solution { public int rob(int[] nums) { if (nums.length == 0) { return 0; } // 存儲當前位置，下一個位置，和再下一個位置的結果 int current = 0; int next_1 = 0; int next_2 = 0; // 動態規劃，利用中間結果，尋找最大值 for (int i = nums.length - 1; i >= 0; i--) { current = Math.max( // 當前不偷 next_1, // 當前偷 nums[i] + next_2 ); next_2 = next_1; next_1 = current; } return current; } }
總結
以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題主要利用動態規劃就可以解決，可以改寫遞歸，優化空間複雜度。
