Leetcode 198. House Robber | XINDOO

原题链接：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]); 
    }
}