HouseRobber系列问题（DP）

这里我们看一下Leet上面 HouseRobber 系列问题，这里都是用 动态规划（DynamicProgramming）来做的。需要理解一下动态规划的相关知识。

1. HouseRobber

给出一个数组代表每一个商户的钱。要求选出不连续的n个商户，使得加起来的钱最多。
用例：[1,2,3,1] ==> 4 这里抢 1,3
[2,1,1,2] ==> 4 这里抢 2,2

分析

如果单单看 [1,2,3,1] 这个用例很容易把题目理解成在数组中选奇数个或者偶数个的问题。写了代码，Submit。发现出来错误的用例，即第2个用例。其实不是简单的奇数个偶数个的问题，是复杂一点的问题。

思路

这里是一个求极值的问题，是典型的动态规划的问题。对于动态规划，最关键的一步就是寻找 递推公式。
具体到这个问题上，从后往前想（从结果出发）：到第n家，抢到最大钱数的结果分为两种情况---（1）抢第n家，即不能抢第n-1家，再加上之前(n-2) 家抢到的最大钱数。（2）不抢第n家，即之前 （n-1）家抢到的最大钱数。所以最终的递推公式为：
我们维护一个等长的数组，用于存储当前位置可以获得最大的钱数，最终返回该数组的最后一个元素即可。

代码

package day_34;

import com.sun.xml.internal.ws.encoding.MtomCodec;

//   不能取连续的元素，然后取出和最大的元素。
//   对实现方式没有要求。
//   求极值的问题首先考虑 DynamicProgramming。
//   抢到第n家时候，要么不抢n-1家，这时候是前 n-2家+第n家
//                要么不抢第n家，是前 n-1 家抢的
//   这里新建一个 dp 数组用于存储到第n家时候抢到的钱
public class HouseRobber {
    public int rob(int[] nums){
            int dp[] = new int[nums.length];
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0],nums[1]);
            for(int i=2;i<nums.length;i++){
            dp[i] = Math.max(nums[i]+dp[i-2],dp[i-1]);
            }
            return dp[dp.length-1];
    }

    public static void main(String args[]){
        int a[] = {2,1,1,2};
        HouseRobber h = new HouseRobber();
        System.out.println(h.rob(a));
    }
}