方法：記憶化搜索（遞歸）

思路：

和爬樓梯幾乎是同一個模板的。爬樓梯是memo[i] = res1 + res2;，而打家劫舍是memo[i] = Math.max(res1, res2);

后來忽然發現了一個細微的差別，爬樓梯，緩存一般是開n+1位，而打家劫舍緩存一般開n位就夠了。

1. 使用memo記憶，緩存已經探索過的節點
2. 從數組最后一個值開始往前探索
   • 遞歸結束判斷：如果索引超出范圍，則返回
   • 如果memo有值，用緩存值
   • 對于當前探索的i這個節點，能不能偷，有兩個情況：
     • 情況一：偷i-1家，那么i家就不能偷（遞歸進去探索i-1節點）
     • 情況二：偷i-2家，那么i家也能偷（遞歸進去探索i-2節點）
     • 返回兩種情況的較大值，順便保存到記憶

class Solution {public int rob(int[] nums) {int n = nums.length;// 記憶（緩存），默認未使用標志為-1int[] memo = new int[n];Arrays.fill(memo, -1);// 從索引n-1開始搜索（也就是數組的最后一個值）return dfs(n - 1, nums, memo);}private int dfs(int i, int[] nums, int[] memo) {// 索引超出范圍，返回if (i < 0) {return 0;}// 如果已經判斷過這種情況了，直接用記憶（緩存）if (memo[i] != -1) {return memo[i];} else {// 情況一：偷i-1家，那么i家就不能偷// 情況二：偷i-2家，那么i家也能偷int res1 = dfs(i - 1, nums, memo);int res2 = dfs(i - 2, nums, memo) + nums[i];// 返回兩種情況的較大值，順便保存到記憶memo[i] = Math.max(res1, res2);}return memo[i];}
}

從dfs函數來看，一進去先判斷索引是否超出范圍，超出了則返回。其實是浪費多了一次資源（因為調用函數要壓棧，出棧等，時間空間都變慢了）

可以改成這樣：先判斷索引，再考慮調用函數：

private int dfs(int i, int[] nums, int[] memo) {if (memo[i] != -1) {return memo[i];} else {// 先判斷索引合法，再調用函數int res1 = 0;if (i - 1 >= 0) {res1 = dfs(i - 1, nums, memo);}// res2要賦值為nums[i]int res2 = nums[i];if (i - 2 >= 0) {res2 = dfs(i - 2, nums, memo) + nums[i];}memo[i] = Math.max(res1, res2);}return memo[i];
}

注意，這里res2要默認賦值為nums[i]。因為這是一個決策，是決定偷i-2，那么i家先偷了，再去i-2，然后發現i-2沒有人住（超出索引范圍），那么i家我也偷到了。

如果寫成這樣是錯的：

private int dfs(int i, int[] nums, int[] memo) {if (memo[i] != -1) {return memo[i];} else {int res1 = 0;int res2 = 0;if (i - 1 >= 0) {res1 = dfs(i - 1, nums, memo);}if (i - 2 >= 0) {res2 = dfs(i - 2, nums, memo) + nums[i];}memo[i] = Math.max(res1, res2);}return memo[i];
}

方法：動態規劃（遞推）

思路：

遞推要初始化,因為f[i]需要依賴f[i-1]和f[i-2]，所以要初始化前兩個數，還要特判n==1的情況。

class Solution {public int rob(int[] nums) {int n = nums.length;// 如果只有一家，直接偷，返回。if (n == 1) {return nums[0];}int[] f = new int[n];// 遞推要初始化,因為f[i]需要依賴f[i-1]和f[i-2]，所以要初始化前兩個數f[0] = nums[0];f[1] = Math.max(nums[0], nums[1]);// 從第三個數開始遍歷for (int i = 2; i < n; i++) {// 情況一：偷i-1家，那么i家就不能偷// 情況二：偷i-2家，那么i家也能偷int res1 = f[i - 1];int res2 = f[i - 2] + nums[i];// 偷較大值f[i] = Math.max(res1, res2);}// 最后的結果，在最后一家判斷完之后，包含了所有的情況。// 所以答案在最后一個索引的位置。return f[n - 1];}
}

思路：

把f數組索引直接+2。上一篇代碼的f[0]的值，放到這一題代碼的f[2]的位置。

不管f[0]和f[1]，直接不用他們。

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

思路：

空間優化的寫法。

class Solution {public int rob(int[] nums) {int f0 = 0;int f1 = 0;for (int x : nums) {int newF = Math.max(f1, f0 + x);f0 = f1;f1 = newF;}return f1;}
}

這些都是寫完之后的優化版本，如果第一次寫，不要想復雜的，先按照自己內心第一思路，把題目寫完先，再想優化。

方法：動態規劃（遞推）

思路：

• 特判索引0位置，把剩余位置變為非循環數組進行操作。
• 索引0位置只有兩種選擇，偷或者不偷。
  • 偷索引0，那么索引1和索引n-1不能偷。問題變為從索引2到n-2的非循環數組。
  • 不偷索引0。問題變為從索引1到n-1的非循環數組。
• 取二者較大值

class Solution {public int rob(int[] nums) {int n = nums.length;// 偷索引0，那么索引1和索引n-1不能偷。問題變為從索引2到n-2的非循環數組。int res1 = nums[0] + rob1(nums, 2, n - 2);// 不偷索引0。問題變為從索引1到n-1的非循環數組。int res2 = rob1(nums, 1, n - 1);// 取二者較大值return Math.max(res1, res2);}// 上一題的空間優化版本private int rob1(int[] nums, int start, int end) {int f0 = 0;int f1 = 0;// [start,end] 左閉右閉for (int i = start; i <= end; i++) {int newF = Math.max(f1, f0 + nums[i]);f0 = f1;f1 = newF;}return f1;}
}

方法：動態規劃（遞推）

思路：

• 兩邊互相獨立，求一邊，最后f[n] * f[n]即可。
• 初始化f[0]和f[1]。如果沒有空地，只有不放這1種選擇；如果只有一塊空地，有放和不放2種選擇。
• 對于每個f[i]：
  • 情況一：如果不放f[i]的話，f[i-1]可放可不放
  • 情況二：如果放f[i]的話, f[i-2]可放可不放
  • 兩種情況加起來，就是f[i]可放可不放
• 最后返回結果時：
  • 注意，兩個MOD相加，不會溢出int。但是兩個MOD相乘，會溢出int
  • 所以要先轉為long，相乘，取模，后再轉為int

class Solution {public int countHousePlacements(int n) {// 兩邊互相獨立，求一邊，最后f[n] * f[n]即可final int MOD = 1000000007;int[] f = new int[n + 2];// 初始化。如果沒有空地，只有不放這1種選擇；如果只有一塊空地，有放和不放2種選擇。f[0] = 1;f[1] = 2;for (int i = 2; i <= n; i++) {// 情況一：如果不放f[i]，f[i-1]可放可不放// 情況二：如果放f[i], f[i-2]可放可不放// 兩種情況加起來，就是f[i]可放可不放f[i] = (f[i - 1] + f[i - 2]) % MOD;}// 注意，兩個MOD相加，不會溢出int。但是兩個MOD相乘，會溢出int// 所以要先轉為long，相乘，取模，后再轉為intreturn (int) ((long) f[n] * f[n] % MOD);}
}

總感覺這道題跟《打家劫舍》沒什么關系，反而像是《爬樓梯》。每個位置都可爬可不爬，然后結果加起來。f[i] = (f[i - 1] + f[i - 2])。初步是這么想，多做題，回頭再看看。

關于取模運算，可以看@靈艾山茶府的這篇文章：模運算的世界：當加減乘除遇上取模。