本文主要是介绍代码随想录：动态规划29-31，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
198.打家劫舍
题目
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。
代码
class Solution {public int rob(int[] nums) {//特殊值：只有一个房屋if(nums.length == 1){return nums[0];}int n = nums.length; //房屋数量//dp[i]表示走到偷到第i个房屋的金额最大值int[] dp = new int[n];//dp初始化dp[0] = nums[0];dp[1] = Math.max(nums[0], nums[1]);//遍历顺序：从前往后for(int i=2; i < n; i++){//递推公式：当前金额由前一个和前两个位置转移而来//偷：前两个位置的金额+当前金额//不偷：前一个位置的金额dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);}return dp[n-1];}
}213.打家劫舍II
题目
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。
代码
class Solution {public int rob(int[] nums) {int n = nums.length; //房屋数量//特殊值：房屋数量=1if(n == 1){return nums[0];}//特殊值：房屋数量=2if(n == 2){return Math.max(nums[0], nums[1]);}//房屋成环的情况下，首尾元素必然不能同时取到//情况1：考虑头不考虑尾//情况2：考虑尾不考虑头，然后取两者的最大值int max1 = demo(nums, 0, n-2); //首部前n-1个房屋int max2 = demo(nums, 1, n-1); //尾部后n-1个房屋return Math.max(max1,max2);}public int demo(int[] nums, int start, int end){//dp数组的长度得是n，而不是n-1//情况1：用到dp的前n-1的位置//情况2：用到dp的后n-1的位置int[] dp = new int[nums.length];//初始化：情况1[0,n-2],情况2[1,n-1]dp[start] = nums[start];dp[start+1] = Math.max(nums[start], nums[start+1]);for(int i=start+2; i <= end; i++){dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);}return dp[end];}
}总结
成环的情况首尾元素不能同时偷，因此，单独分两种情况考虑，一种是考虑前面的肯定不偷尾元素，一种是考虑后面的肯定不偷首元素，然后两者取最大值。
337.打家劫舍III
题目
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
示例 1:
输入: root = [3,2,3,null,3,null,1] 输出: 7 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
代码
class Solution {public int rob(TreeNode root) {//dp[0]表示不偷该节点的最大金额//dp[1]表示偷该节点的最大金额int[] dp = new int[2]; dp = traverse(root); //后序遍历得到根节点不偷和偷的最大金额return Math.max(dp[0],dp[1]);}//后序遍历二叉树：返回值是长度2的数组int[] traverse(TreeNode root){int[] res = new int[2]; //dp数组//终止条件：空节点if(root == null){//空节点的不偷和偷最大金额都是0（dp数组初始化{0,0}）return res; }//单层逻辑int[] left = traverse(root.left); //左子节点不偷和偷的最大金额int[] right = traverse(root.right); //右子节点不偷和偷的最大金额//中间节点（递推公式）//当前节点不偷=左子节点最大金额+右子节点最大金额res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); //偷当前节点=该节点金额+左孩子不偷的金额+右孩子不偷的金额res[1] = root.val + left[0] + right[0]; return res;}
}这篇关于代码随想录：动态规划29-31的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
