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

本文主要是介绍代码随想录算法训练营第四十八天 _ 动态规划_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];}
}