代码随想录算法训练营第四十八天 _ 动态规划_198.打家劫舍、213.打家劫舍II、337.打家劫舍 III。

学习目标：

动态规划五部曲：
① 确定dp[i]的含义
② 求递推公式
③ dp数组如何初始化
④ 确定遍历顺序
⑤ 打印递归数组 ---- 调试
引用自代码随想录！

60天训练营打卡计划！

学习内容：

198.打家劫舍

• 动态规划五步曲：
  ① 确定dp[i]的含义 ： 包含 下标i 偷得最大的金币数。
  ② 求递推公式 ： dp[i] = max(dp[i-2] + nums[i] , dp[i-1])
  偷 i：dp[i-2] + nums[i]
  不偷 i：dp[i-1]
  ③ dp数组如何初始化 ： dp[0] = nums[0] dp[1] = max(nums[0], nums[1])
  ④ 确定遍历顺序 ： 从前向后

// 动态规划
class Solution {
    public int rob(int[] nums) {
        int size = nums.length;
        int[] dp = new int[size];

        // 初始化
        dp[0] = nums[0];
        if(size > 1)
            dp[1] = Math.max(nums[0], nums[1]);

        // 递归逻辑
        for(int i = 2; i < size; i++){
            dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
        }

        return dp[size-1];
    }
}

213.打家劫舍II

• 给定的数组连城环啦。
• 动态规划五步曲：
  ① 确定dp[i]的含义 ：包含 下标i 偷得最大的金币数。
  ② 求递推公式 ： dp[i] = max(dp[i-2] + nums[i] , dp[i-1])
  偷 i：dp[i-2] + nums[i]
  不偷 i：dp[i-1]
  ③ dp数组如何初始化 ： dp[start] = nums[start]
  dp[start+1] = Math.max(nums[start],nums[start+1])
  ④ 确定遍历顺序 ： 从前向后

class Solution {
    public int robAsist(int[] nums, int start, int end) {

        // 包含 物品i 在内的最大的金币数。
        int[] dp = new int[end];

        // 初始化
        dp[start] = nums[start];
        dp[start+1] = Math.max(nums[start],nums[start+1]);

        // 递归逻辑
        for(int j = start+2; j < end; j++){
            dp[j] = Math.max(dp[j-1], dp[j-2]+nums[j]);
        }

        return dp[end-1];
    }

    public int rob(int[] nums) {
        if(nums.length == 1)   return nums[0];
        if(nums.length == 2)   return nums[0] > nums[1] ? nums[0] : nums[1];
        int len = nums.length;
        //  因为是环，有两种情况
        // 一、不选择头节点，这样就可以选尾节点
        // 二。不选择尾节点，这样就可以选头节点
        // 且规则是左闭右开
        return Math.max(robAsist(nums, 0, len - 1), robAsist(nums, 1, len));
    }
}

337.打家劫舍 III

• 树形的数据结构。（后序遍历 – 左右中）
• 递归三部曲：
  递归函数的传入参数和返回值；
  递归函数的结束条件；
  递归函数的最小逻辑。
• 动态规划五步曲：
  ① 确定dp[i]的含义 ： dp[0] : 不偷当前节点的最大金币数 dp[1]：偷当前节点的最大金币数
  ② 求递推公式 ： 递归传给上一层
  偷根节点： dp[1] = node.val + leftdp[0] + rightdp[0]
  不偷根节点： dp[0] = max(leftdp[0]，leftdp[1]) + max(rightdp[0]，rightdp[1])
  ③ dp数组如何初始化 ： dp[0] = 0 dp[1] = 0
  ④ 确定遍历顺序 ： 从叶子节点到根节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 递归函数的返回值是一维数组。
    public int[] robTree(TreeNode node) {
        // 递归函数的结束条件
        if(node == null) return new int[]{0,0};

        // 递归函数的最小逻辑
        int[] leftdp = robTree(node.left);
        int[] rightdp = robTree(node.right);
        
        // 不偷根节点
        int val1 = Math.max(leftdp[0], leftdp[1]) + Math.max(rightdp[0], rightdp[1]);
        // 偷根节点
        int val2 = node.val + leftdp[0] + rightdp[0];

        return new int[]{val1, val2};
    }
    
    public int rob(TreeNode root) {
        int[] dp = robTree(root);
        return dp[0] > dp[1] ? dp[0] : dp[1];
    }
}

学习时间：

• 上午两个半小时，整理文档半小时。