# 198. House Robber (1d to 2d, 1d, fib) ![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MesXoWaJccsaNGFP-6R%2F-Met2ZL416TGRIayHL-W%2Fimage.png?alt=media\&token=3683c659-c8f1-4d30-8c52-a85364df1318) ![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MesXoWaJccsaNGFP-6R%2F-Met2bBWuHRNZRZQUn1S%2Fimage.png?alt=media\&token=84ebff4b-f10a-4398-9633-5e84fd2fd73f) ## DFS - over time limit ```java class Solution { public int rob(int[] nums) { return dfs(nums, 0); } private int dfs(int[] nums, int i) { if (i >= nums.length) { return 0; } int case1 = nums[i] + dfs(nums, i+2); // 第i天偷, i+2 天才能偷 int case2 = dfs(nums, i+1); // 第i天不偷, i+1天可以偷 return Math.max(case1, case2); } } ``` ## DFS + memo T: O(n) S: O(n) ```java class Solution { public int rob(int[] nums) { Integer[] memo = new Integer[nums.length+1]; return dfs(nums, 0, memo); } private int dfs(int[] nums, int i, Integer[] memo) { if (i >= nums.length) { return 0; } if (memo[i] != null) { return memo[i]; } int case1 = nums[i] + dfs(nums, i+2, memo); int case2 = dfs(nums, i+1, memo); memo[i] = Math.max(case1, case2); return memo[i]; } ja ``` same ```java class Solution { public int rob(int[] nums) { return dp(nums, 0, new Integer[nums.length]); } private int dp(int[] nums, int start, Integer memo[]) { if (start >= nums.length) { return 0; } if (memo[start] != null) { return memo[start]; } int result = 0; result += Math.max(nums[start] + dp(nums, start+2, memo), dp(nums, start+1, memo)); return memo[start] = result; } } /* [1,2,3,1] x x max( nums[i] + dp(i+2) // rob i dp(i+1) // not rob i ) r. x. i = 0 /\ /\ x r x i = 1 / / /\ r x r x i = 2. -> duplicate sub problems [1,2,3,1] r x x r x r x r. -> duplicate sub before memo: O(2^n), choose or not choose after memo: O(2n) */ ``` ## dp #### 注意 限制是不能連續偷 ``` 子問題 狀態定義 dp 方程 0~i 可以偷的房子, dp[i] 能偷到的最大金額 => dp[i], 表示能偷的 max value => dp[i] = dp[i-1] + ??? or what? ``` ``` for (0~n-1) dp[i] = dp[i-1] + nums[i] => 可以嗎？ => dp[i-1] 的結果＋搶第i個房子（num[i]) 但其實 dp[i-1] 不確定會不會去偷, 所以... 爾且如果偷了 dp[i-1], 就不會偷 nums[i] 所以要多加信息, 到底有沒有偷, 所以多加 "一維" ``` #### 多加一維後 ``` dp[i][0,1] => 0 不偷, 1偷 第 i 天不偷, 所以 i-1 天可以 偷, 也可以 不偷, 兩者選一個大的 a[i][0] = Max(a[i-1][0], a[i-1][1]) 第i天偷, 所以 i-1 天不能偷, 然後第 i 天必偷（所以把 nums[i]算上 a[i][1] = Max(a[i-1][0], 0) + nums[i] ``` ``` so 開始來寫程式, 初始值 a[0][0] = 0; // 第一間房子不偷 a[0][1] = nums[0]; // 第一間房子要偷 然後因為題目有說是非負整數 所以 Max(a[i-1][0], 0) => a[i-1][0] => a[i][1] = a[i-1][0] + nums[i] 最後可以寫出下面的代碼！ 注意最後回傳 return Math.max(dp[n-1][0], dp[n-1][1]); ``` time: O(n) space: O(2n) ```java class Solution { public int rob(int[] nums) { // add one more dim, 0: not steal, 1: steal // dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]) // dp[i][1] = dp[i-1][0] + nums[i] 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]); } } ``` ## 更優化的方式, top down ``` 不用二維的話呢？ 第i個房子 可偷 或 不偷 dp 變成 dp[i] = max(dp[i-1] 偷 , dp[i-2]偷 + 第i間必偷) => dp[i] = max(dp[i-1] , dp[i-2] + nums[i]) ps. dp[i-3], dp[i-4]... 不用考慮嗎？ 不用！ dp[i-2] 肯定包含且大於 dp[i-3], dp[i-4]... like dp[i] = ...dp[i-1], dp[i] 一定是大於 dp[i-1] 對吧？ ``` time: O(n) space: O(n) ```java class Solution { public int rob(int[] nums) { if (nums.length == 1) { return nums[0]; } int[] dp = new int[nums.length]; dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < nums.length; i++) { dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]); } return dp[nums.length-1]; }, } ``` ## button up 非常精簡, 只是空間要多 2 ```java class Solution { public int rob(int[] nums) { if (nums.length == 1) { return nums[0]; } int[] dp = new int[nums.length+2]; // needs more space for first for (int i = nums.length - 1; i >= 0; i--) { dp[i] = Math.max(dp[i+1], nums[i] + dp[i+2]); } return dp[0]; } } ``` ## 更優化 最後, 既然都只剩 dp\[i-1] 和 dp\[i-2], 是不是可以像 fib 一樣, 用兩個變數來存？ time: O(n) space: O(1) ```java class Solution { public int rob(int[] nums) { if (nums.length == 1) { return nums[0]; } int prevMax = 0; int currMax = 0; for (int num : nums) { int temp = currMax; currMax = Math.max(prevMax + num, currMax); prevMax = temp; } return currMax; } } ``` 這樣寫好像更簡單哈... 為了只用變數, 再計算完 dpi (最新的答案後 我們要把 dpi 保留到下一 round, 還有 dpi1 保留, dpi2 可以丟棄 保留 dpi1, dpi so dpi2 = dpi1 dpi1 = dpi
```java class Solution { pub lic int rob(int[] nums) { if (nums.length == 1) { return nums[0]; } int dpi2 = 0; int dpi1 = 0; int dpi = 0; for (int i = nums.length - 1; i >= 0; i--) { dpi = Math.max(dpi1, nums[i] + dpi2); dpi2 = dpi1; dpi1 = dpi; } return dpi; } } ``` ````java ```java class Solution { public int rob(int[] nums) { int n = nums.length; if (nums.length == 1) { return nums[0]; } int prevMax = nums[0]; int currentMax = Math.max(nums[0], nums[1]); for (int i = 2; i < n; i++) { int max = Math.max(prevMax + nums[i], currentMax); prevMax = currentMax; currentMax = max; } return currentMax; } } ``` ```` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/198.-house-robber-1d-to-2d.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.