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

代码随想录算法训练营第四十八天|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。
今天回顾了一下树的遍历，整体还是做递归遍历结合前、中、后序遍历去做逻辑。
学习了打家劫舍的解题方法，整体处理的逻辑还是讨论当前节点抢还是不抢。如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子（注意这里说的是“考虑”）