国家合同模板网站,青岛企业建站程序,长春市建设集团股份有限公司,住房与城乡建设网上办事大厅学习目标#xff1a; 动态规划五部曲#xff1a; ① 确定dp[i]的含义 ② 求递推公式 ③ dp数组如何初始化 ④ 确定遍历顺序 ⑤ 打印递归数组 ---- 调试 引用自代码随想录#xff01; 60天训练营打卡计划#xff01;
学习内容#xff1a;
198.打家劫舍
动态规划五步曲 动态规划五部曲 ① 确定dp[i]的含义 ② 求递推公式 ③ dp数组如何初始化 ④ 确定遍历顺序 ⑤ 打印递归数组 ---- 调试 引用自代码随想录 60天训练营打卡计划
学习内容
198.打家劫舍
动态规划五步曲 ① 确定dp[i]的含义 包含 下标i 偷得最大的金币数。 ② 求递推公式 dp[i] max(dp[i-2] nums[i] , dp[i-1]) 偷 idp[i-2] nums[i] 不偷 idp[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]) 偷 idp[i-2] nums[i] 不偷 idp[i-1] ③ dp数组如何初始化 dp[start] nums[start] dp[start1] Math.max(nums[start],nums[start1]) ④ 确定遍历顺序 从前向后
class Solution {public int robAsist(int[] nums, int start, int end) {// 包含 物品i 在内的最大的金币数。int[] dp new int[end];// 初始化dp[start] nums[start];dp[start1] Math.max(nums[start],nums[start1]);// 递归逻辑for(int j start2; 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];}
}学习时间
上午两个半小时整理文档半小时。
