2025-3-24 leetcode刷题情况（动态规划——01背包）

一、416.分割等和子集

1.题目描述

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

2.代码

3.思路

首先进行边界检查，若数组为空则直接返回 false。接着计算数组元素总和，若总和为奇数，由于无法将其平分为两个相等和的子集，所以直接返回 false；若为偶数，计算目标和 target 为总和的一半。然后创建一个长度为 target + 1 的动态规划数组 dp，用于记录能否组成和为不同值的情况。之后遍历数组中的每个元素，对于每个元素，从 target 开始逆向遍历到该元素的值，更新 dp 数组。更新规则是取当前 dp[j] 和 dp[j - nums[i]] + nums[i] 中的较大值，这是在考虑是否将当前元素纳入子集以组成和为 j 的情况。最后，判断 dp[target] 是否等于 target，若相等则说明可以将数组分割成两个和相等的子集，返回 true；否则返回 false。

二、1049.最后一块石头的重量Ⅱ

1.题目描述

2.代码

3.思路

首先计算所有石头重量的总和 sum，然后得到目标重量 target 为总和的一半（使用右移一位操作实现除以 2）。

接着创建长度为 target + 1 的动态规划数组 dp，dp[j] 表示能组合出的重量不超过 j 的最大重量和。之后遍历每块石头，对于每块石头，从 target 开始逆向遍历到当前石头的重量，更新 dp 数组，取 dp[j] 和 dp[j - stones[i]] + stones[i] 中的较大值，这是在考虑是否把当前石头纳入组合以得到更接近 j 的重量和。

最终，通过 sum - 2 * dp[target] 计算得出最后剩下石头的最小重量。这里的逻辑是将石头分成两堆，dp[target] 是其中一堆能达到的最接近 target 的重量和，另一堆重量为 sum - dp[target]，两者相减就得到最后剩余石头的最小重量。