动态规划总结(三)

House Robber问题属于一维的动规问题，这篇文章给大家介绍一下。

1，House Robber
一个小偷去一条街上偷东西，假设这条街上有n个房子，每个房子里都有特定的现金，但是小偷不能偷连续的房子，那样会触发警报，问怎样才能偷到最多的钱。

我们把这条街抽象成一个数组，数组里的值代表了房子里现金的数目，假设小偷拿了第0个房子的钱，那么第1个房子的钱就不能拿，否则就会触发警报。我们创建一个数组result[]，result[i]代表了到第i个房子小偷最多能得到的钱数，result[i] = Math.max(result[i - 1], result[i-2] + nums[i - 1]) (i > 2)，这就是递推式，这样我们一直计算到最后一个房子，我们就得到了现金最大的方案。代码如下：

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

2，House Robber II
这道题是第一道题的变形，这里假设这条街是个环状，就是第一个房子和最后一个房子也是相连的，也就是说，如果拿了第一个房子里的钱，最后一个房子的钱就不可以拿。

处理这个问题我们可以把它分成两个子问题，第一个拿第一个房子的钱，这样就不能哪最后一个房子里的钱； 第二个是不拿第一个房子的钱，这样就可以拿最后一个房子的钱；我们分别计算出最优值，然后进行比较，取一个最大值就是我们要找的解。代码如下：

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