213. House Robber II 首尾相同的偷竊問題

［抄題］：

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are?arranged in a circle.?That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and?it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight?without alerting the police.

Example 1:

Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),because they are adjacent houses.

Example 2:

Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).Total amount you can rob = 1 + 3 = 4.

?[暴力解法]：

時間分析：

空間分析：

?[優化后]：

時間分析：

空間分析：

［奇葩輸出條件］：

［奇葩corner case］：

［思維問題］：

不知道怎么處理首尾重復的問題：分情況討論。從0-n-1, 1-n

［英文數據結構或算法，為什么不用別的數據結構或算法］：

［一句話思路］：

exclude必須是用上一次的結果i e，否則會越加越大。所以要把上一次的結果用i e保存起來。

［輸入量］：空：?正常情況：特大：特小：程序里處理到的特殊情況：異常情況（不合法不合理的輸入）：

［畫圖］：

［一刷］：

［二刷］：

［三刷］：

［四刷］：

［五刷］：

? [五分鐘肉眼debug的結果]：

［總結］：

分情況討論也是一種辦法。

［復雜度］：Time complexity: O(n) Space complexity: O(1)

［算法思想：迭代/遞歸/分治/貪心］：

［關鍵模板化代碼］：

［其他解法］：

［Follow Up］：

［LC給出的題目變變變］：

?[代碼風格] ：

?[是否頭一次寫此類driver funcion的代碼] ：

?[潛臺詞] ：

class Solution {public int rob(int[] nums) {//corner caseif (nums == null || nums.length == 0) return 0;if (nums.length == 1) return nums[0];//discuss in 2 waysreturn Math.max(rob(nums, 0, nums.length - 2), rob(nums, 1, nums.length - 1));}public int rob(int[] nums, int low, int high) {//define include, excludeint include = 0; int exclude = 0;//for loop, define i and e, and expandfor (int j = low; j <= high; j++) {int i = include; int e = exclude;include = e + nums[j];exclude = Math.max(i, e);}//return maxreturn Math.max(include, exclude);}
}

?