动态规划：打家劫舍---鹏-程-万-里

各位小伙伴，大家好！上周我们给出了一篇动态规划系列的字符串匹配。详情可以点击链接进行查看（动态规划：字符串匹配）~本周我们再推一篇动态规划的题目，LeetCode打家劫舍系列。

打家劫舍I

LeetCode198---打家劫舍I【简单】 题目描述

题目描述

给定一个数组，每个元素都是正整数，我们需要在不连续获取相邻元素的情况下，使得数组中总和最大的结果。

1、解题思路

这道题的难度级别被归类为简单题目也有一定的原因。根据题意，我们很容易得到动态规划的3个基本要素

动态规划的数组定义，dp[i]的定义为：小偷在第i家时，能够获取的最大的金额。在dp[i]位置，小偷都可以有偷或者不偷的选择，当选择偷窃的时候，那么第i-1家一定处于没有被偷窃的状态，此时状态转移方程：dp[i] = dp[i-2]+nums[i]当选择不偷窃的时候，此时dp[i]的资产情况与dp[i-1]是相同的，所以此时的状态的方程为：dp[i]=dp[i-1]综上所述，我们的动态转移方程为：dp[i] = max(dp[i-2] + nums[i] , dp[i-1])动态规划的初始条件：根据上面的动态方程可以发现，当我们把i=0或者i=1带入的时候，会得到dp[-2]和dp[-1]的情况，这显然是不存在的，所以我们可以将不存在的情况设置为负无穷，所以就可以得到对应的初始条件对于第一个元素：dp[0]=nums[0]对于第二个元素：dp[1] = max(nums[0],nums[1])

当动态规划的两个条件完成之后，我们就可以实现对应的代码了！

2、代码实现public int rob(int[] nums) { int len = nums.length; //判断特殊情况 if(len < 1) return 0; if(len == 1) return nums[0]; if(len == 2) return Math.max(nums[0],nums[1]); //初始化 int[] ans = new int[len]; ans[0] = nums[0]; ans[1] = nums[0]>nums[1]?nums[0]:nums[1]; for(int i = 2 ; i < len ; i++){ //ans[i]可以分为两种，i-2时盗窃了，那么加上此次的盗窃，或者i-1时盗窃了，那么此次将无法继续盗窃 ans[i] = Math.max(ans[i-2]+nums[i],ans[i-1]); } return ans[len-1]; }打家劫舍II

Leetcode213 --- 打家劫舍II【中等题】 题目描述

题目描述

在上一道题的基础上，此题增加了一个新的条件，对于整个数组而言，我们需要认为数组的首尾是相互连接的。

1、解题思路

此时我们需要将整个数组分做情况来处理，具体的情况小白画了一个示意图给大家参考一下！

解题思路

主要有上面的三种情况可以取消环的限制。

第一种：去掉整个数组的两端，我们对整个数组只取1~n-2的区域。第二种：去掉数组的末尾，对数组的0~n-2进行计算第三种：去掉数组的开头，对数组的1~n-1进行计算

然后我们再进行简化，由于当前数组的所有元素都是正整数，而情况二和情况三都包含了情况一，并且我们的目标是求取最大值，所以情况一的结果一定小于等于情况二和三。因此在编写实现代码的时候，我们就可以舍弃情况一，仅对后两种情况取最大值就可以了！

当我们计算后两种情况的时候，我们就又将其转化为了第一题的问题，然后直接套用第一题的代码即可！但是此处我们又进行了另一种优化。

代码优化

在上一题的代码中，我们发现在每次使用dp数组的时候，其实仅仅是使用i元素的前两个数值而已，分别是dp[i-2]和dp[i-1]，那么我们也可以对其进行简化，使用两个变量来分别代表这两个元素dp[i-2]和dp[i-1]。此时我们的空间复杂度将会从O(n)改变为O(1)。

2、代码实现public int rob(int[] nums) { //将整个环形分为两种情况来计算，从0~n-2和1~n-1 if(nums == null || nums.length == 0) return 0; int len = nums.length ; if(len == 1) return nums[0]; return Math.max(help(nums,0,len-2) , help(nums,1,len-1)); } private int help(int[] nums , int start , int end){ int dpi1 = 0; int dpi2 = 0; int dpi = 0; for(int i = end ; i >= start ; i--){ dpi = Math.max(nums[i] + dpi2 , dpi1); dpi2 = dpi1; dpi1 = dpi; } return dpi; }打家劫舍III

leetcode337 --- 打家劫舍III【中等题】 题目描述

题目描述

在这道题中，我们将数组换为了二叉树，我们需要进行隔层“偷窃”。

1、解题思路

在这道题中，我们依旧是使用动态规划进行处理。我们再次来分析动态规划的三个要素：

动态数组的状态定义：分析题目可以知道，我们需要记录的每个节点的最大值，所以我们的状态数组dp需要记录两个信息，一个是当前的节点，另一个是当前小偷到达当前节点时，能够获得的最大的金额。所以我们可以使用一个map来进行存储。状态转移方程：由于我们使用的是二叉树，在二叉树中，我们只能不断的向下进行遍历，无法获取前期的状态，即：我们无法得知dp[i-2]和dp[i-1]的状态，因此我们需要换一种思维，从后向前进行遍历，即：dp[i] = max(dp[i+2] + nums[i] , dp[i+1])。所以状态返程为：当前节点选择偷取，则当前节点的值为：cur = root.val + rob(root.left.left) + rob(root.left.right) + rob(root.right.left) + rob(root.right.right)如果不选择当前节点，则应该交给下一层节点进行调用：cur = rob(root.left) + rob(root.right)基本状态：当我们遍历到空节点的时候，返回一个0值即可。2、代码实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { //动态规划中的备忘录 HashMap<TreeNode, Integer> memo = new HashMap<>(); public int rob(TreeNode root) { if(root == null) return 0; //判断当前的root是否已经计算过了 if(memo.containsKey(root)){ return memo.get(root); } //选择当前节点 int cur = root.val; if(root.left != null){//下一次的选择将会到达下一层 cur += rob(root.left.left) + rob(root.left.right); } if(root.right != null){//下一次的选择将会到达下一层 cur += rob(root.right.left) + rob(root.right.right); } //不选择当前节点 int next = rob(root.left) + rob(root.right); int res = Math.max(cur,next); //存入备忘录中 memo.put(root,res); return res; } } ---来自腾讯云社区的---鹏-程-万-里