Leetcode 198. House Robber

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

原题链接：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表示不偷和偷。

代码如下：

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]); 
    }
}