代码随想录 Day48 - 动态规划（九）
作者：jjn0703
- 2023-08-22 江苏
本文字数：1563 字
阅读完需：约 5 分钟
作业题
198. 打家劫舍
package jjn.carl.dp;
import java.util.Scanner;
/** * @author Jjn * @since 2023/8/22 21:45 */public class LeetCode198 { public int rob(int[] nums) { // dp[i] 到第i件物品，最大的价值 int[] dp = new int[nums.length]; dp[0] = Math.max(dp[0], dp[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 static void main(String[] args) { Scanner scanner = new Scanner(System.in); int count = scanner.nextInt(); int[] nums = new int[count]; for (int i = 0; i < nums.length; i++) { nums[i] = scanner.nextInt(); } int robbed = new LeetCode198().rob(nums); System.out.println(robbed); }}
复制代码
分两种情况，分别计算，套用打家劫舍 1 里面的做法即可。
package jjn.carl.dp;
import java.util.Arrays;import java.util.Scanner;
/** * @author Jjn * @since 2023/8/22 23:12 */public class LeetCode213 { public int rob(int[] nums) { if (nums == null || nums.length == 0) { return 0; } if (nums.length == 1) { return nums[0]; } if (nums.length == 2) { return Math.max(nums[0], nums[1]); } int first = robRange(Arrays.copyOfRange(nums, 0, nums.length - 1)); int second = robRange(Arrays.copyOfRange(nums, 1, nums.length)); return Math.max(first, second); } private int robRange(int[] nums) { int[] f = new int[nums.length]; f[0] = nums[0]; f[1] = Math.max(nums[0], nums[1]); for (int i = 2; i < nums.length; i++) { f[i] = Math.max(f[i - 1], f[i - 2] + nums[i]); } return f[nums.length - 1]; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int count = scanner.nextInt(); int[] nums = new int[count]; for (int i = 0; i < count; i++) { nums[i] = scanner.nextInt(); } int robbed = new LeetCode213().rob(nums); System.out.println(robbed); }}
复制代码
树形 DP，通过两个 HashMap，分别存放是否要偷和偷的结果。
class Solution { /** * Choose current node. */ private final Map<TreeNode, Integer> chosen = new HashMap<>(); /** * Do not choose current node. */ private final Map<TreeNode, Integer> givenUp = new HashMap<>(); public int rob(TreeNode root) { dfs(root); return Math.max(chosen.getOrDefault(root, 0), givenUp.getOrDefault(root, 0)); } private void dfs(TreeNode root) { if (root == null) { return; } dfs(root.left); dfs(root.right); chosen.put(root, root.val + givenUp.getOrDefault(root.left, 0) + givenUp.getOrDefault(root.right, 0)); givenUp.put(root, Math.max(chosen.getOrDefault(root.left, 0), givenUp.getOrDefault(root.left, 0)) + Math.max(chosen.getOrDefault(root.right, 0), givenUp.getOrDefault(root.right, 0))); }}复制代码
划线
评论
复制
发布于: 刚刚阅读数: 5
版权声明: 本文为 InfoQ 作者【jjn0703】的原创文章。
原文链接:【http://xie.infoq.cn/article/cd89287232591280654e97a70】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
jjn0703
关注
Java工程师/终身学习者 2018-03-26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论