算法-动态规划（三）
今天继续我们的动态规划专题，集中练习一些有关动态规划的题，加深印象。
👉👀💬今日练习（一）打家劫舍II（LeetCode-213）。
去偷一条环形街的房屋，每个屋里都有数量不等的钱，用数组nums来表示所有屋里的金额。
⚠️注意，如果偷相邻两个屋就会触发报警，且第一家和最后一家屋子是连在一起的环形，计算在不触发报警的情况下，你一晚最多能偷到多少，返回最大值。如：
输入：[1,3,3]输出：3--------------输入：[2,7,9,3,1]输出：11=2+9
🙇思路：
依旧是动态规划，还是我们之前强调的：
定义子问题，
找出状态转移，即子问题的递推关系
确定【填表】的计算顺序
空间优化，这前期可以先放一放，等熟练了在来考虑。
此题的难点是环形，也就是说，如果偷第一家就不能偷最后一家，偷最后一家就不能偷第一家，有了这个结论，再应用动态规划也就简单了，我们只需要分开两种情况：
偷第一家，不偷最后一家，在剩下的0~N-1个屋里偷；
不偷第一家，偷最后一家，在剩下的1~N个屋里偷。
代码：
public int rob(int[] nums) {int len=nums.length;if(len<1){return 0;}if(len<2){return nums[0];}// 注意这里传值是数组下表而不是长度。return Math.max(myrob(nums,0,len-2),myrob(nums,1,len-1));}private int myrob(int[] nums ,int start,int end){int prev=nums[start];if(start >= end){return prev;}int curr=Math.max(nums[start+1],prev);for(int i=start+2;i<=end;i++){int temp=curr;curr=Math.max(curr,prev+nums[i]);prev=temp;}return curr;}
复杂度分析
时间复杂度：O(N)，两次遍历nums的线性时间。
空间复杂度：O(1)，我们用到curr和prev，使用常数大小的空间。
👉👀💬今日练习（二）打家劫舍III（LeetCode-337）。
先说明一下，这道题不是动态规划的解法，不过既然做到了打家劫舍，就把这个系列的都做完得了。
此题中，小偷去偷一个树形结构的街道，仍旧是相邻两个屋不能偷，计算能偷到的最大金额。如：
输入: [3,2,3,null,3,null,1]3/ \2 3\ \3 1输出: 7解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.输入: [3,4,5,1,3,null,1]3/ \4 5/ \ \1 3 1输出: 9解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.
🙇思路：
此题中，房屋的结构变为树形结构，且相邻房屋不能偷，也就是说树中的父子节点不能同时偷，所以此题的思路分析为：
偷父节点，两个相邻的房屋（子节点）就不能偷，这就相当于我们要找出孙子节点中能偷到的最大金额加父节点的金额。
不偷父节点，此时要找出两个子节点能偷到的最大金额。
🙋解法一：暴力递归。
public int rob(TreeNode root) {if(root==null){return 0;}int res = root.val;if(root.left != null){res+=rob_1(root.left.left)+rob_1(root.left.right);}if(root.right != null){res+=rob_1(root.right.left)+rob_1(root.right.right);}return Math.max(res,rob_1(root.left)+rob_1(root.right));}
🙋解法二：暴力递归+记忆化。
在解法一中，我们每一次的递归都计算了当前节点、子节点和孙子节点，所以这儿我们引入记忆化，解决重复计算的问题。
public int rob(TreeNode root) {HashMap<TreeNode, Integer> map = new HashMap<>();return rob_2_helper(root,map);}private int rob_2_helper(TreeNode root, Map<TreeNode,Integer> map){if(root==null){return 0;}if(map.containsKey(root)){return map.get(root);}int res = root.val;if(root.left != null){res+=rob_2_helper(root.left.left,map)+rob_2_helper(root.left.right,map);}if(root.right != null){res+=rob_2_helper(root.right.left,map)+rob_2_helper(root.right.right,map);}int money = Math.max(res,rob_2_helper(root.left,map)+rob_2_helper(root.right,map));map.put(root,money);return money;}
🙋解法三：
🙇思路：
上面两种解法每次递归中，都需要计算孙子节点，虽然加了记忆化但仍旧耗时。此解法的思路可能头一回看的话，有点懵，但是确实是个很好很棒的解析思路。
此解法中，我们引入一个长度为2的数组res，用于记录当前节点是否去偷，res[0]表示不偷自己，res[1]表示偷自己；相连的两个节点不能同时去偷。任意一个节点能偷到钱可以表示为：
当前节点选择不偷，当前节点能偷到的最大金额=左孩子能偷到的最大金额+右孩子能偷到的最大金额。公式表示为：
res[0] = max(left[0]+left[1]) + max(right[0],right[1])当前节点选择偷，当前节点能偷到的最大金额=左孩子不偷自己时能偷到的最大金额+右孩子不偷自己时能偷到的最大金额。公式表示为：
res[1] = left[0]+right[1]+root.val
代码：
public int rob(TreeNode root) {int[] res=helper(root);return Math.max(res[0],res[1]);}private int[] helper(TreeNode node){int[] res = new int[2];if(node == null){return res;}int[] left = helper(node.left);int[] right=helper(node.right);res[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);res[1] = left[0]+right[0]+node.val;return res;}
不积跬步，无以至千里。
文章有帮助的话，点个转发、在看呗
。
谢谢支持哟 (*^__^*)
END
👇