原题链接：198. House Robber
一句话理解题意，有个偷马贼晚上要偷尽可能值钱的马，但连续两头马被偷会触发报警，问他如何在不触发报警（不偷连续的两匹马）的情况下偷到总价值最高马，返回最高总价值。
看到maximum，就应该想到这是应该求解最优的问题，一想到求解最优，一般除了暴力就是动态规划了。
我们先来看看暴力解法，此题暴力还是比较复杂的，枚举每个位置的马偷或者不偷，用递归可以很简单的实现，然后再排除连续的情况。想想时间复杂度，已经到了惊人的O(2^n),一般n到20左右一般的计算机就抗不住了。
如果是动态规划又会怎么样？如果robber在第i个位置，他如何保证在此位置获得最大的价值，他肯定有两种选择，偷或者不偷第i匹马。如果偷的情况下最大价值是啥？不偷又是啥？如果你想通了，你肯定会得到两种情况下的转态转移方程。偷第I批马 dp[1][i] = Math.max(dp[1][i-1], dp[0][i-1]+nums[i])，不偷 dp[0][i] = Math.max(dp[0][i-1], dp[1][i-1])。 这里我用 0和1表示不偷和偷。
本人Java代码如下：
public class Solution {
public int rob(int[] nums) {
if (0 == nums.length)
return 0;
int[][] dp = new int[2][nums.length];
for (int i = 0; i < nums.length; i++) {
if (0 == i) {
dp[0][0] = 0;
dp[1][0] = nums[0];
}
else if (1 == i) {
dp[0][1] = nums[0];
dp[1][1] = nums[1];
}
else {
dp[0][i] = Math.max(dp[0][i-1], dp[1][i-1]);
dp[1][i] = Math.max(dp[1][i-1], dp[0][i-1]+nums[i]);
}
}
return Math.max(dp[0][nums.length-1], dp[1][nums.length-1]);
}
}
