算法笔记|Day34动态规划VII

本文主要是介绍算法笔记|Day34动态规划VII，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

☆☆☆☆☆leetcode 198.打家劫舍

题目链接：leetcode 198.打家劫舍

题目分析

1.dp数组含义：dp[i]表示考虑下标i（包括i）以内的房屋，最多可以偷窃的金额。；
2.递推公式：dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1])（如果偷第i个房间则为dp[i-2]+nums[i]；如果不偷第i个房间则为dp[i-1]，两者取最大值）；
3.初始化：dp[0]=nums[0]，dp[1]=Math.max(nums[0],nums[1])（dp[0]表示下标为0的房间最多偷窃的金额为nums[0]，dp[1]表示从下标为0到1的房间最多偷窃的金额为Math.max(nums[0],nums[1]）；
4.遍历顺序：从小到大。

代码

class Solution {public int rob(int[] nums) {if(nums.length==1)return nums[0];int dp[]=new int[nums.length];dp[0]=nums[0];dp[1]=Math.max(nums[0],nums[1]);for(int i=2;i<nums.length;i++)dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);return dp[nums.length-1];}
}

☆☆☆☆☆leetcode 213.打家劫舍II

题目链接：leetcode 213.打家劫舍II

题目分析

对于一个数组，成环主要有三种情况：①考虑不包含首尾元素；②考虑包含首元素，不包含尾元素；③考虑包含尾元素，不包含首元素。事实上情况②或③均包括情况①，所以仅需考虑情况②和③中的最大值即可。
1.dp数组含义：dp[i]表示考虑下标i（包括i）以内的房屋，最多可以偷窃的金额。；
2.递推公式：dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1])（如果偷第i个房间则为dp[i-2]+nums[i]；如果不偷第i个房间则为dp[i-1]，两者取最大值）；
3.初始化：dp[0]=nums[0]，dp[1]=Math.max(nums[0],nums[1])（dp[0]表示下标为0的房间最多偷窃的金额为nums[0]，dp[1]表示从下标为0到1的房间最多偷窃的金额为Math.max(nums[0],nums[1]）；
4.遍历顺序：从小到大。

代码

class Solution {public int rob(int[] nums) {if(nums.length==1)return nums[0];return Math.max(rob1(nums,0,nums.length-2),rob1(nums,1,nums.length-1));}public int rob1(int[] nums,int start,int end){if(start==end)return nums[start];int dp[]=new int[end-start+2];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-2]+nums[i],dp[i-1]);return dp[end];}
}

☆☆☆☆☆leetcode 337.打家劫舍 III

题目链接：leetcode 337.打家劫舍 III

题目分析

1.dp数组含义：dp[0]表示不偷该节点最多可以偷窃的金额，dp[1]表示偷该节点最多可以偷窃的金额；
2.递推公式：dp[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1])（不偷该节点，要考虑左右子节点最多偷窃的金额总和，且左右子节点各自偷窃的金额最多为偷该节点与不偷该节点的最大值），dp[1]=root.val+left[0]+right[0]（偷该节点，最多偷窃的金额总和为该节点金额与左右节点不偷最多偷窃的金额的和）；
3.初始化：如果root=null，则返回{0,0}]；
4.遍历顺序：后序遍历（左右中）。

代码

class Solution {public int rob(TreeNode root) {return Math.max(traversal(root)[0],traversal(root)[1]);}public int[] traversal(TreeNode root){int dp[]=new int[2];if(root==null)return dp;int left[]=traversal(root.left);int right[]=traversal(root.right);dp[0]=Math.max(left[0],left[1])+Math.max(right[0],right[1]);dp[1]=root.val+left[0]+right[0];return dp;  }
}

这篇关于算法笔记|Day34动态规划VII的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---