【动态规划算法】之打家劫舍Ⅰ

1.打家劫舍Ⅰ

打家劫舍是dp解决的经典问题，动规五部曲分析如下：

• 1.确定dp数组（dp table）以及下标的含义
  dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。

• 2.确定递推公式
  决定dp[i]的因素就是第i房间偷还是不偷。
  （1）如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
  （2）如果不偷第i房间，那么dp[i] = dp[i - 1]，
  即考虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点）
  然后dp[i]取最大值：
  即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);

• 3.dp数组如何初始化
  从递推公式dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]
  从dp[i]的定义上来讲，

  • dp[0] 一定是 nums[0]；
  • dp[1]就是nums[0]和nums[1]的最大值
    即：dp[1] = max(nums[0], nums[1]);

• 4.确定遍历顺序
  dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的，那么一定是从前到后遍历！

• 5.举例推导dp数组
  以示例二，输入[2,7,9,3,1]为例。
  0 1 2 3 4
  2 7 11 11 12

代码如下

public  int rob(int[] nums) {
    	//1.特殊情况
        if (nums.length==0 ||nums==null){
            return 0;
        }
        if (nums.length==1){
            return nums[0];
        }
        int[] dp=new int[nums.length];
    	//2.初始化
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
   		//3.遍历
        for (int i = 2; i <nums.length ; i++) {
            //如果偷第i个 那么应该是dp[i-2]+nums[i]
            //如果不偷第i个就可以考虑偷第i-1个 dp[i-1]
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }
}