代码随想录算法训练营第42天| 198.打家劫舍、213.打家劫舍II 337.打家劫舍III、 337.打家劫舍III
198.打家劫舍
记忆化搜索思路：
可以从最后一间房子开始，每次面对一个房子要考虑打劫还是不打劫，如果打劫了就从它的下下个房子开始打劫，在这个过程中打劫还是不打劫可以组成一个二叉树。如图，val是索引
然后这个过程中可以使用记忆化搜索来记录已经算过的值，从而实现剪枝。
动态规划思路：
和上面的想法类似，决定dp[i]的因素就是第i房间偷还是不偷。
如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。如果不偷第i房间，那么dp[i] = dp[i - 1]，即考 虑i-1房。
递推公式：dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
不同题解：
//记忆化搜索
public int rob0(int[] nums) {
int n = nums.length;
int[] memo = new int[n];
Arrays.fill(memo, -1);
return dfs(nums, memo, n - 1); // 从最后一个房子开始思考,选和不选可以组成一个二叉树,利用记忆化搜索对二叉树剪枝
}
public int dfs(int[] nums, int[] memo, int i) {
if (i < 0) {
return 0;
}
if (memo[i] != -1)
return memo[i];
memo[i] = Math.max(dfs(nums, memo, i - 1), dfs(nums, memo, i - 2) + nums[i]);
return memo[i];
}
//动态规划
public int rob1(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(dp[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
//优化空间
public int rob2(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int[] dp = new int[3];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
dp[2] = dp[1];
for (int i = 2; i < nums.length; i++) {
dp[2] = Math.max(dp[1], dp[0] + nums[i]);
dp[0] = dp[1];
dp[1] = dp[2];
}
return dp[2];
}
213.打家劫舍II
题目链接：213.打家劫舍II
文档讲解：代码随想录
状态：不会
思路：连成环之后就导致了第一个和最后一个房间最多只能同时打劫一次，其他位置就没有影响了。所以可以将环拆成两个队列，如图所示:
剩下的和198.打家劫舍 就是一样的了。
题解：
public int rob(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int res1 = robby(Arrays.copyOfRange(nums, 0, nums.length - 1));
int res2 = robby(Arrays.copyOfRange(nums, 1, nums.length));
return Math.max(res2, res1);
}
public int robby(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int pre2 = nums[0];
int pre1 = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
int cur = Math.max(pre1, pre2 + nums[i]);
pre2 = pre1;
pre1 = cur;
}
return pre1;
}
337.打家劫舍III
题目链接：337.打家劫舍III
文档讲解：代码随想录
状态：不会
思路：
对于树的话，首先就要想到遍历方式，前中后序（深度优先搜索）还是层序遍历（广度优先搜索）。
本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算。
如果还是利用考虑i-1和考虑i-2的思路的话，就需要考虑儿子节点和儿子的儿子节点，但是这样最多需要考虑四个节点的情况，所以可以将选和不选该节点的最大和作为返回值，这样就不要考虑儿子的儿子了。
题解：
// 在二叉树中可以偷窃的最大金额
public int rob(TreeNode root) {
// 调用深度优先搜索函数获取结果数组
int[] res = dfs(root);
// 返回可以偷窃的最大金额，即res[0]和res[1]中的最大值
return Math.max(res[0], res[1]);
}
// 深度优先搜索函数，后序遍历，返回一个数组，数组的两个元素分别表示
// res[0]: 偷当前节点的最大金额
// res[1]: 不偷当前节点的最大金额
public int[] dfs(TreeNode root) {
// 如果当前节点为空，返回{0, 0}
if (root == null) {
return new int[]{0, 0};
}
// 递归计算左子树的结果
int[] left = dfs(root.left);
// 递归计算右子树的结果
int[] right = dfs(root.right);
// 计算偷当前节点的最大金额
// 等于左子树不偷的最大金额 + 右子树不偷的最大金额 + 当前节点的值
int rob = left[1] + right[1] + root.val;
// 计算不偷当前节点的最大金额
// 等于左子树和右子树的最大金额（不管偷还是不偷）
int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
// 返回当前节点的结果数组
return new int[]{rob, notRob};
}
原文地址：https://blog.csdn.net/weixin_43903745/article/details/140144666
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！