打家劫舍系列(力扣198、213、337)Java动态规划
一、打家劫舍(力扣198)
198. 打家劫舍-力扣
此题的动态规划有两种思路:
1、思路一:
可以参考前面相同题型的题解:https://bbs.huaweicloud.com/blogs/406132
房屋只有两种状态:被偷 和 没被偷
那么我们用dp数组来记录第i间房屋时的最大金额,dp[i][0] 记录被偷的情况,dp[i][1]记录没被偷的情况。
dp[i][0]表示被偷,那么前一间必然没有被偷,当前值就是前一间没有被偷的情况下的金额+当前金额,则dp[i][0] = dp[i-1][1] + nums[i]
dp[i][1]表示没被偷,那么前一间可能被偷,也可能没被偷,当前值就是这两种情况中较大的那个,则dp[i][1] = max{ dp[i-1][0] , dp[i][1] }
最后取dp[len-1][0]和dp[len-1][1]的较大值即可。考虑到当前房屋值只与前一间房屋有关,则可以用变量来代替dp数组,就成了下面的代码。
在买卖股票的题解(上面的链接)中有此方法更详细的讲解和推导过程,感兴趣的朋友可以去看一下。
class Solution {
public int rob(int[] nums) {
int a = nums[0];
int b = 0;
for(int i=1; i<nums.length; i++) {
int tempA = a;
int tempB = b;
a = tempB + nums[i];
b = Math.max(tempA, tempB);
}
return Math.max(a, b);
}
}
2、思路二
对于第k间房屋,只有两种情况:被偷 和 不被偷
如果被偷,当前金额为k-2间房屋的金额+当前金额
如果不被偷,当前金额为k-1间房屋金额
这间房屋的金额就是两个值中较大的那个,所以得到递推公式:
dp[i]=max(dp[i−2]+nums[i],dp[i−1])
class Solution {
static int max = 0;
public int rob(int[] nums) {
if(nums.length==1){
return nums[0];
}
int c = nums[0];
int b = Math.max(nums[0], nums[1]);
int a = nums[0];
for(int i=2; i<nums.length; i++){
a = Math.max(b, (c+nums[i]));
c = b;
b = a;
}
return Math.max(a, b);
}
}
二、打家劫舍II(力扣213)
这题与上题的不同在于,最后一家与第一家连在了一起,而我们动态规划出来的结果是无法知道第一家是否被偷的。那么,我们是不是可以分而治之,分为第一家被偷和第一家没被偷两种情况去看,这样问题就迎刃而解了。
其中,偷东西的那部分代码可以抽取成方法,这样代码会更加简洁,但是分开写比较容易看清思路。
class Solution {
public int rob(int[] nums) {
int res;
int len = nums.length;
if(len == 1) {
return nums[0];
}
if(len == 2) {
return Math.max(nums[0], nums[1]);
}
//第一间偷了
int a;
int b;
if(len==3) {
res = nums[0];
} else {
a = nums[2];
b = 0;
for(int i=3; i<len-1; i++) {
int tempA = a;
int tempB = b;
a = tempB + nums[i];
b = Math.max(tempA, tempB);
}
res = Math.max(a, b) + nums[0];
}
//第一间没偷
a = nums[1];
b = 0;
for(int i=2; i<len; i++) {
int tempA = a;
int tempB = b;
a = tempB + nums[i];
b = Math.max(tempA, tempB);
}
res = Math.max(res, Math.max(a, b));
return res;
}
}
三、打家劫舍III(力扣337)
337. 打家劫舍 III-力扣
这次要偷的房子组成了一棵二叉树,我们简化一下题目:二叉树的节点上有权值,要求不能同时取父子节点的权值,问最大权值和是多少?
首先,每个节点有两个状态:被偷 和 没被偷。我们使用a(i)来表示第i个节点被偷时,他和他的子树所贡献的最大权值;使用b(i)表示第i个节点不被偷时,他和他的子树所贡献的最大权值。那么:
因为a(i)表示被偷,所以他的子节点不能被偷,那么他的权值和是左右子树不被偷时的权值和+当前节点权值,即:
a(i) = b(i.left) + b(i.right) + i.val;
因为b(i)表示当前节点不被偷,那么他的左右节点可以被偷也可以不被偷,我们取权值和较大的情况,即:
b(i) = max{a(i.left) , b(i.left)} + max{a(i.right) , b(i.right)}
最终我们找出a(root) 和 b(root)中的较大值即可。a和b可考虑用哈希表来保存。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
Map<TreeNode, Integer> a; //a.get(root) 表示当前节点被偷时,他和他的子树所能贡献的最大价值
Map<TreeNode, Integer> b; //b.get(root) 表示当前节点没被偷时,他和他的子树所能贡献的最大价值
public int rob(TreeNode root) {
a = new HashMap<>();
b = new HashMap<>();
dfs(root);
return Math.max(a.get(root), b.get(root));
}
void dfs(TreeNode node) {
if(node == null) {
return;
}
dfs(node.left);
dfs(node.right);
a.put(node, b.getOrDefault(node.left, 0)+b.getOrDefault(node.right, 0)+node.val);
b.put(node,
Math.max(a.getOrDefault(node.left, 0), b.getOrDefault(node.left, 0))
+ Math.max(a.getOrDefault(node.right, 0), b.getOrDefault(node.right, 0)));
}
}
不难看出,当前的ab值只与他的左右子树的ab值有关,所以,可以考虑将每次调用时的ab值返回给上一级调用,这样可以省去哈希表。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int rob(TreeNode root) {
int []res = dfs(root);
return Math.max(res[0], res[1]);
}
int[] dfs(TreeNode node) {
if(node == null) {
return new int[]{0, 0};
}
int []left = dfs(node.left);
int []right = dfs(node.right);
//表示当前节点被偷时,他和他的子树所能贡献的最大价值
int a = left[1] + right[1] + node.val;
//表示当前节点没被偷时,他和他的子树所能贡献的最大价值
int b = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
return new int[]{a, b};
}
}
- 点赞
- 收藏
- 关注作者
评论(0)