代码随想录算法训练营第四十六天 _ 动态规划_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];}
}
学习时间：
- 上午两个半小时，整理文档半小时。