You are a PRofessional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that 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.

第二遍做法（推薦做法）：

DP：我們維護一個一位數組dp，其中dp[i]表示到達 index = i 位置時不相鄰數能形成的最大和，i不一定是最后一個rob的房子

dp[0] = num[0];

dp[i] = max(dp[i-1], i>=2? dp[i-2]+num[i] : num[i]);

時間復雜度： O(N), 空間復雜度： O(N) ->O(1)

 1 public class Solution { 2     public int rob(int[] num) { 3         if (num==null || num.length==0) return 0; 4         int[] res = new int[num.length]; 5         res[0] = num[0]; 6         for (int i=1; i<num.length; i++) { 7             res[i] = Math.max(res[i-1], i>=2? res[i-2]+num[i] : num[i]); 8         } 9         return res[num.length-1];10     }11 }

第一遍做法：

DP，一維數組dp[i] 表示 以 index = i 房子作為最后一個rob的房子的最大搶劫金額

dp[0] = num[0];

dp[i] = max{dp[0], dp[1], ... dp[i-2]} + num[i];

最后return的是dp[0].....dp[num.length-1]中的最大值

雖然這個思路在這里略麻煩，O（N^2）, 但不失為一個好思路

 1 public class Solution { 2     public int rob(int[] num) { 3         if (num==null || num.length==0) return 0; 4         int[] res = new int[num.length]; 5         res[0] = num[0]; 6         if (num.length > 1) res[1] = num[1]; 7         for (int i=2; i<num.length; i++) { 8             int maxVal = 0; 9             for (int j=0; j<i-1; j++) {10                 maxVal = Math.max(maxVal, res[j]);11             }12             res[i] = maxVal + num[i];13         }14         int result = 0;15         for (int i=0; i<num.length; i++) {16             result = Math.max(result, res[i]);17         }18         return result;19     }20 }