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

2023-12-24 10:36:49
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];
    }
}

文章来源:https://blog.csdn.net/m0_48904153/article/details/135177105
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。