组合总和IV | LeetCode-377 | 动态规划

发表于 2024-10-07 更新于 2024-11-13 分类于算法， LeetCode ，动态规划阅读次数：阅读次数： Waline：本文字数： 4.5k 阅读时长 ≈ 7 分钟

动态规划练习题

题目1：198. 打家劫舍

1.题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

2.题解

class Solution {
    // 定义一个公共方法rob，用来计算打劫非相邻房屋可以获得的最大金额
    public int rob(int[] nums) {
        //判断特殊情况
        if (nums == null || nums.length == 0) return 0;
		if (nums.length == 1) return nums[0];

        // 初始化一个动态规划数组dp，长度等于输入数组nums的长度
        int[] dp = new int[nums.length];
        
        // 如果只有一个房屋，那么最大金额就是这个房屋里的金额
        dp[0] = nums[0];
        
        // 如果有两个房屋，选择金额较大的那个房屋
        dp[1] = Math.max(nums[0], nums[1]);
        
        // 从第三个房屋开始遍历
        for (int i = 2; i < nums.length; i++) {
            // 对于每个房屋i，有两种选择：
            // 1. 不打劫房屋i，那么前一步的最大金额保持不变，即dp[i-1]
            // 2. 打劫房屋i，那么当前的最大金额为前两步的最大金额加上当前房屋的金额，即dp[i-2] + nums[i]
            // 取两种情况下的最大值作为dp[i]的值
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        
        // 返回最后一个房屋的最大金额
        return dp[nums.length - 1];
    }
}

题目2：213. 打家劫舍 II

1.题目描述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例 1：

1
2
3

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 3：

1 2	输入：nums = [1,2,3] 输出：3

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 1000

2.题解

// 定义一个名为 Solution 的类
class Solution {
    // 主方法，用于计算能够偷窃的最大金额
    public int rob(int[] nums) {
        // 如果输入数组为空或长度为0，则表示没有房子可以偷，返回0
        if (nums == null || nums.length == 0) return 0;
        // 如果只有一个房子，直接返回该房子的金额
        if (nums.length == 1) return nums[0];
        
        // 分别计算两种情况下的最大可偷金额：
        // 第一种情况：不偷最后一个房子，从第一个到最后第二个
        int result1 = robRange(nums, 0, nums.length - 2);
        // 第二种情况：不偷第一个房子，从第二个到最后一个
        int result2 = robRange(nums, 1, nums.length - 1);
        // 返回两种情况下较大的金额
        return Math.max(result1, result2);
    }

    // 辅助方法，用于计算从 start 到 end 范围内房间的最大可偷金额
    public int robRange(int[] nums, int start, int end) {
        // 如果开始和结束位置相同，表示只有一个房子，直接返回该房子的金额
        if (start == end) return nums[start];
        // 初始化动态规划数组，长度与输入数组相同
        int[] dp = new int[nums.length];
        // 填充初始条件
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);
        // 从第三个房子开始遍历
        for (int i = start + 2; i <= end; i++) {
            // 动态规划状态转移方程：当前房子的收益等于前天（i-2）的最大收益加上当前房子的价值，
            // 或者昨天（i-1）的最大收益（即不偷当前房子）
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        // 返回最后一个房子位置处的最大可偷金额
        return dp[end];
    }
}

题目3：337. 打家劫舍 III

1.题目描述

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

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

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

示例 1:

1
2
3

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

示例 2:

1
2
3

输入: root = [3,4,5,1,3,null,1]
输出: 9
解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9

提示：

树的节点数在 $[1, 10^4]$ 范围内
$0 <= Node.val <= 10^4$

2.题解

2.1 递归-超时

class Solution {
    public int rob(TreeNode root) {
        //递归
        if(root == null) return 0;
        int money = root.val;
        if(root.left != null){
            money += rob(root.left.left) + rob(root.left.right);
        }
        if(root.right != null){
            money += rob(root.right.left) + rob(root.right.right);
        }
        return Math.max(money,rob(root.left)+rob(root.right));
    }
}

2.2 记忆化递归

class Solution {
    Map<TreeNode,Integer> map = new HashMap<>();
    public int rob(TreeNode root) {
        //递归优化
        if(root == null) return 0;
        if(root.left == null && root.right == null) return root.val;
        if(map.containsKey(root)) return map.get(root);

        //偷父节点
        int money1 = root.val;
        if(root.left != null){
            money1 += rob(root.left.left) + rob(root.left.right);
        }
        if(root.right != null){
            money1 += rob(root.right.left) + rob(root.right.right);
        }

        //不偷父节点
        int money2 = rob(root.left)+rob(root.right);

        map.put(root,Math.max(money1,money2));
        return Math.max(money1,money2);
    }
}

2.3 动态规划

class Solution {
    /**
     * 主方法，计算以 root 为根的二叉树能抢劫的最大金额。
     * @param root 树的根节点。
     * @return 返回能抢劫的最大金额。
     */
    public int rob(TreeNode root) {
        // 计算从根节点开始的子树抢劫策略
        int[] result = robTree(root);
        // 返回偷或不偷根节点时的最大金额
        return Math.max(result[0], result[1]);
    }

    /**
     * 辅助递归方法，计算从 cur 节点开始的子树的最佳抢劫策略。
     * @param cur 当前节点。
     * @return 返回一个数组，其中 result[0] 是不偷当前节点的最大金额，result[1] 是偷当前节点的最大金额。
     */
    public int[] robTree(TreeNode cur) {
        // 如果当前节点为空，直接返回不偷也不抢的情况
        if (cur == null) return new int[]{0, 0};

        // 递归计算左右子树的抢劫策略
        int[] left = robTree(cur.left);
        int[] right = robTree(cur.right);

        // 偷当前节点，那么它的左右子节点都不能偷
        int money1 = cur.val + left[0] + right[0];
        // 不偷当前节点，那么其左右子节点可以选择偷或不偷
        int money2 = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);

        // 返回当前节点的最优策略
        return new int[]{money2, money1};
    }
}

-------------本文结束感谢您的阅读-------------