打家劫舍的智慧！

阅读：评论：0

打家劫舍的智慧！

大家好，我是bigsai，好久不见，甚是想念！

今天给大家分享经典的打家劫舍系列，力扣和牛客上都有，普通dp变形优化还有个树形dp，不得不说，现在这年头太卷了，小偷也得会算法，太难了！

打家劫舍(一)

你是一个经验丰富的小偷，准备偷沿街的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家；如果偷了第二家，那么就不能偷第一家和第三家。

给定一个整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

通过题意我们知道我们需要替小偷找到一个最好的偷路，让小偷偷的最多，但是有个规则就是不能连续偷两家。然后如果采用暴力排列组合的方式有太多种，我们从其中一边考虑选择一个策略向另一端偷起，并且每个位置偷不偷和上面位置结果有关系，例如6户人家可能最大偷的结果从下面产出(能偷就偷情况)，数值越大情况种类越多：

这是个动态规划的问题，下面开始分析思考一下。

首先确定dp[]数组，dp[i]表示前i家偷到的最大值(这里第i个可用可不用，注意有人可能会从以第i个为结尾偷的最大值，大家可以自行考虑不过需要记录最大值)。

然后确定递推式，这个部分一定要有一定的全局观，就是假设前面的dp已知找下一个结果和前面的联系，和递归有一点像的，我们分析dp[i]结果和前面结果的联系，到第i户人家的结果其实无非有两种可能性，偷第i户人家和不偷第i户人家，如果不偷第i户人家，那么偷到的最大值和偷前i-1户人家的值一致，那么dp[i]=dp[i-1];如果偷第i户人家的，那么说明第i-1户人家的不能偷，但是i-2户人家的可以偷，所以就是前i-2户人家偷到的最大值加上第i户人家的钱财，那么dp[i]=dp[i-2]+nums[i];

然后确定初始化值，我们根据递推式知道前两项肯定是需要特殊考虑的，我们需要考虑dp[0]和dp[1]的值，dp[0]没得选有的偷肯定偷第0户人家的所以dp[0]=nums[0].而dp[1]可能是偷第0户人家也可能是偷第1户人家的，但是因为两个连续的不能偷所以取最大的dp[1]=max(nums[0],nums[1]);

就这样获得完整的状态转移方程为：

dp[0]=nums[0]  
dp[1]=max(nums[0],nums[1])
dp[i]=dp[i-2]+nums[i]  //i>=2

具体实现的代码为：

public int rob (int[] nums) {// write code here//特殊情况 考虑一下if(nums.length==0) return 0;if(nums.length==1) return nums[0];int dp[]=new int[nums.length];dp[0]=nums[0];//只能偷第0户dp[1]=Math.max(nums[0],nums[1]);//第0户和第一户谁有钱偷谁for(int i=2;i<nums.length;i++){dp[i]=Math.max(nums[i]+dp[i-2],dp[i-1]);}return  dp[nums.length-1];
}

打家劫舍(二)

你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。

给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

这个和前面打家劫舍(一)的区别就是第一个房间和最后一个房间视为相邻形成一个闭环，即以前有些能偷类型的现在不能再偷了。例如6个人家下面的第二种情况就不能再偷了。

这个问题只是这个边界这个多了这个限制，其他条件没变的，所以还是地地道道的动态规划问题，只不过需要我们考虑一下边界条件。

如何考虑呢?

很容易啊，打破这个首尾连续的情况即可！ 害怕第一户和最后一户连续，那么拆开讨论就行了，进行两次动态规划：

第一户人家如果不偷，那么最后一户人家是可偷可不偷的，那么可以初始第一户不偷dp跑到最后一家获得一个第一户不偷的最大值。

第一户人家如果偷，那么最后一户人家一定不能偷(否则连续)，但是倒数第二家无所谓可偷可不偷，那么可以初始第一家偷dp跑到倒数第二家获得一个第一户偷的最大值。

取两种情况的最大值就是获得的结果了：

在代码实现上，这里稍微优化了一下从dp[1]表示第一户人家前面dp[0]用来正常参与循环计算。

public int rob (int[] nums) {// write code hereint dp[]=new int[nums.length+1];dp[0]=0;dp[1]=nums[0];//偷第一户int va=dp[1];for(int i=2;i<nums.length;i++){dp[i]=Math.max(nums[i-1]+dp[i-2],dp[i-1]);}va=dp[nums.length-1];//前len-1户的dp值dp[1]=0;//第一户不偷for(int i=2;i<nums.length+1;i++){dp[i]=Math.max(nums[i-1]+dp[i-2],dp[i-1]);}if(dp[nums.length]>va)va=dp[nums.length];//前len户的dp值return va;}

打家劫舍(三)

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

给定二叉树的 root 。返回在不触动警报的情况下，小偷能够盗取的最高金额。

img

这个问题其实转化成一个入门级别的树形dp，而树形dp一般需要借助递归回来的过程计算结果，因为子节点是呈分散所以不能自顶向下

而要自下向顶计算的，向上的过程就是需要借助递归计算子节点的结果的，然后还需要考虑叶子节点的情况即可。我们只需要先考虑其中的局部推导整个上下节点dp值即可。

这里面说了每个节点可偷可不偷，并且连在一起的节点不能一起偷，所以对于每个节点要多保存一个一定不偷的状态，这样才能向上进行dp，不然就会被 两个直接相连的房子 这个条件卡死不能继续运算。

在具体运算时候，每个节点需要保存两个最大值，即可偷和 一定偷，这个也很容易，我们递归函数传递一个大小为2的一维数组即可，遇到null 返回[0,0]这样叶子节点也满足递归，具体实现的代码为：

class Solution {public int rob(TreeNode root) {int result[]=dfs(root);return Math.max(result[0],result[1]);}private int[] dfs(TreeNode root) {int res[]=new int[2];//0 表示不偷最大   1表示可偷最大if(root==null)return res;int left[]=dfs(root.left);int right[]=dfs(root.right);res[0]=left[1]+right[1];//自己不用 儿子可用可不用res[1]=root.val+left[0]+right[0];//自己偷 儿子不偷if(res[0]>res[1])//可偷 看看自己比不偷大不大res[1]=res[0];return res;}
}