代码随想录算法训练营第四十八天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III

发布时间:2024年01月04日

代码随想录算法训练营第四十八天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III

打家劫舍

198.打家劫舍
文章讲解:https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html
题目链接:https://leetcode.cn/problems/house-robber/
视频讲解:https://www.bilibili.com/video/BV1Te411N7SX/

自己看到题目的第一想法

套动态规划五步骤去做,但是没想到切入点,卡在递推公式的推导以及dp的定义上。不知道该如何确定i的概念。

看完代码随想录之后的想法

动态规划去处理该题,i是输入元素的下标,然后递推公式按照i这个索引的元素放不放去推导出来,具体实现:

  • 定义dp数组概念:dp[i]为从0-i个元素中选取多个元素,使这些元素的和最大,同时要满足题目不能选相邻元素的规则。
  • 确定递推公式:递推公式的确定可以从选i和不选i来推导
    • 选i:dp[i]=dp[i-2] + nums[i]。这里用dp[i-2]是因为选了i之后就不能选i-1了。
    • 不选i:dp[i] = dp[i-1]。这里dp[i-1]不一定会选i-1,要多去回顾dp[i]的概念,这里是指从0到i-1中选取多个元素,使这些元素的和最大。
    • 根据选i和不选i最终可以得到推导公式: dp[i] = Math.max(dp[i-2] + nums[i],dp[i-1]);
  • 确定初始化值:dp[0] = nums[0]。dp[1] = Math.max(nums[0],nums[1]);其他元素的值因为是从小到大推的,后面的值由前面推导而来,因此可以直接初始化为0。
  • 确定遍历顺序:因为递推公式是从小到大,所以遍历顺序也从小到大。
  • 打印值

自己实现过程中遇到哪些困难

遍历的时候,i的取值没确定下来,是i<=nums.length还是i<nums.length。
这里思考了一下,因为最终求得后的dp数组要返回的值应该是nums的最后一个元素的位置,因此应该返回dp[nums.length - 1]。并且在遍历过程中,p[i] = Math.max(dp[i-2] + nums[i],dp[i-1]),nums[i]也只能到达i=nums.length - 1,因此这里的循环处理逻辑为i<nums.length。最终代码:

 public int rob(int[] nums) {
     if(nums.length == 1){
         return nums[0];
     }
     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(dp[i-1],dp[i-2] + nums[i]);
     }
     return dp[nums.length - 1];
 }

这道题的核心就是dp[i]的概念和递推公式的确定。

打家劫舍II

213.打家劫舍II 
文章讲解:https://programmercarl.com/0213.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DII.html
题目链接:https://leetcode.cn/problems/house-robber-ii/
视频讲解:https://www.bilibili.com/video/BV1oM411B7xq/

自己看到题目的第一想法

整体思路和打家劫舍第一步一样,区别就是如果是环形的话 那0位置的元素和最后位置的元素不能共存。
这里分2钟场景,一去掉头,二去掉尾,然后看一或者二求出来哪个更大。

看完代码随想录之后的想法

整体方法一样,这里和自己的想法有区别的是自己的想法是做2个nums数组做截取得到[0,length - 1]和[1,length],而代码随想录里是用2个循环去处理。

自己实现过程中遇到哪些困难

初始化值的赋值方式和遍历循环i的初始值和结尾值没确定。
最终代码:

public int rob(int[] nums,int start,int end){
    if (end == start) return nums[start];
    int[] dp = new int[nums.length];
    dp[start] = nums[start];
    dp[start + 1] = Math.max(nums[start],nums[start + 1]);
    for(int i = start + 2; i <= end; i++){
        dp[i] = Math.max(dp[i-2] + nums[i],dp[i - 1]);
    }
    return dp[end];
}

打家劫舍III

337.打家劫舍III
文章讲解:https://programmercarl.com/0337.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8DIII.html
题目链接:https://leetcode.cn/problems/house-robber-iii/
视频讲解:https://www.bilibili.com/video/BV1H24y1Q7sY/

自己看到题目的第一想法

二叉树一样,只是把循环改成树的遍历了,根节点不能打劫左右子节点。
树的遍历有前中后。中为处理计算,前后为递归。

看完代码随想录之后的想法

代码分成2种情况,偷父节点和不偷父节点。

暴力递归:
偷父节点则直接取父节点的值,不偷父节点取2个字节点的值的和。最终再使用Math.max把两种情况下的值做一个比较取大值。

动态规划:
使用一个长度为2的数组,0记录不选根节点的最大值,1记录选根节点的最大值。
树形dp,先搭后序遍历的框架,二叉树的递归需要回归下。
然后再在二叉树递归中增加动态规划逻辑。

public int rob(TreeNode root) {
    // 二叉树一样,只是把循环改成树的遍历了,根节点不能打劫左右子节点
    int[] result = backtracking(root);
    return Math.max(result[0],result[1]);
}
public int[] backtracking(TreeNode node){
    int[] dp = new int[2];
    // 递归三部曲
    // 终止条件
    if(node == null){
        return dp;
    }
    // 后序遍历
    int[] left = backtracking(node.left);
    int[] right = backtracking(node.right);
    // 选当前节点和不选当前节点

    // 选当前节点
    dp[0] = node.val + left[1] + right[1];
    // 不选当前节点
    dp[1] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
    return dp;
}

今日收获&学习时长

这节课整体用的时间不多,大概1.5h。
今天回顾了一下树的遍历,整体还是做递归遍历结合前、中、后序遍历去做逻辑。
学习了打家劫舍的解题方法,整体处理的逻辑还是讨论当前节点抢还是不抢。如果抢了当前节点,两个孩子就不能动,如果没抢当前节点,就可以考虑抢左右孩子(注意这里说的是“考虑”)

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