LC 打家劫舍

LC 打家劫舍

动态规划：dp[][0],dp[][1],0表示没做这件事，1表示做了。

dp[i][0]表示第i+1家（i从0开始）没偷，那么第i家偷没偷都可以，所以dp[i][0] = Max(dp[i-1][0],dp[i-1][1])。

dp[i][1]表示第i+1家偷了，所以上一家肯定没偷，即dp[i][1] = dp[i-1][0] + nums[i];

然后取两者最大值。代码：

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int [][]dp = new int [nums.length][2];
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        int Money = 0;
        for (int i = 1; i < nums.length; i++) {
             dp[i][0] = Math.max(dp[i-1][1],dp[i-1][0]);
             dp[i][1] = dp[i-1][0] + nums[i];
        }
        Money =  Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);
        return Money;
    }
}

 同样，因为每次计算结果只与上一家有关，之前的二维数组的值（即上上家之前的）用不到了，所以可以用两个变量代替dp[i][0]和dp[i][1]。不用用二维数组了，能省空间。

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int dp0,dp1;
        dp0 = 0;
        dp1 = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int temp = dp0;
             dp0 = Math.max(dp0,dp1);
             dp1 = temp + nums[i];
        }
        return Math.max(dp0, dp1);
    }
}