代码随想录算法训练营第四十六天 _ 动态规划_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];}
}

---

学习时间：

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