大家好,我是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 here
int 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;
}
}