你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。计算能够偷到的最多的金额。
条件：给定一个元素为非负整数的数组
先上代码：
public static void main(String[] args) {
int[] ints = {9, 3, 4, 9,11};
int rob = rob(ints);
System.out.println(rob);
}
public static int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[length - 1];
}
反向分析：
这里给定的数组为：{9,3,4,9,11}
dp[]数组是专门用来存取每个房屋数量能够偷到的最大金额
dp[0] 表示只有一个房屋下能够偷到的金额
dp[1] 表示只有两个房屋下能够偷到的金额，num[0]和 num[1]谁的钱多就偷谁的
dp[2]表示有三个房间,这时就要用dp[0]方案的金额加上最后一件房屋的金额和dp[1]方案的金额进行比较
dp[0] = num[0] = 9
dp[1] = num[1]>num[0]?num[1]:num[0]
==> dp[1] = 9
dp[2] = dp[0] + num[2] > dp[1] ? dp[0] + num[2] ：dp[1]
==> dp[2] = 13
dp[3] = dp[1] + num[3] > dp[2] ? dp[1] + num[3] : dp[2]
==> dp[3] = 18
...... 原理就是用dp[i-2]的方案加上num[i]去和dp[i-1]方案进行比较，
且dp[i-2]和dp[i]中间永远隔着一个num[i-1]，也不会存在房屋相隔的情况
