动态规划实战：用智慧解决等和子集与石头重量问题（416，1049）
🤵♂️ 个人主页：@rain雨雨编程
😄微信公众号：rain雨雨编程
✍🏻作者简介：持续分享机器学习，爬虫，数据分析
🐋 希望大家多多支持，我们一起进步！
如果文章对你有帮助的话，
欢迎评论 💬点赞👍🏻 收藏 📂加关注+
目录
416. 分割等和子集
题目描述
思路步骤
代码实现
时间复杂度
空间复杂度
1049. 最后一块石头的重量 II
题目描述
思路步骤
代码实现
时间复杂度
空间复杂度
题目描述
给定一个只包含正整数的非空数组 nums，判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
输出：5
思路步骤
-
计算总和：首先计算数组
nums中所有元素的总和。 -
判断奇偶性：如果总和是奇数，则不可能分割成两个和相等的子集，直接返回
false。 -
初始化动态规划数组：创建一个长度为
sum/2 + 1的布尔数组dp，用于存储从0到sum/2是否可以通过nums中的元素组合得到。 -
填充动态规划数组：遍历数组
nums，对于每个元素nums[i]，从sum/2开始向下遍历dp数组，更新dp[j]的值。 -
检查结果：如果在填充过程中
dp[sum/2]被设置为true，则表示找到了一个和为sum/2的子集，返回true；否则，返回false。
代码实现
class Solution { public boolean canPartition(int[] nums) { // 计算数组总和 int sum = 0; for (int num : nums) { sum += num; } // 如果总和是奇数，则无法分割 int n = nums.length; if (sum % 2 != 0) return false; // 目标和为总和的一半 int target = sum / 2; // 初始化动态规划数组 int[] dp = new int[target + 1]; // 使用动态规划填充dp数组 for (int i = 0; i = nums[i]; j--) { // 如果dp[j-nums[i]]为true，或者dp[j]已经为true，则更新dp[j] dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]); } // 如果找到了和为target的子集，直接返回true if (dp[target] == target) return true; } // 如果遍历结束后dp[target]为target，说明找到了和为target的子集 return dp[target] == target; }}时间复杂度
时间复杂度为 O(n*sum/2)，其中 n 是数组 nums 的长度，sum 是数组元素的总和。这是因为我们需要两层循环，外层循环遍历数组，内层循环从 target 开始向下遍历 dp 数组。
空间复杂度
空间复杂度为 O(sum/2)，这是因为我们使用了一个大小为 sum/2 + 1 的数组 dp 来存储中间结果。由于 sum 是数组元素的总和，这个值最多是数组中所有元素的和，因此空间复杂度与数组中元素的总和成正比。
1049. 最后一块石头的重量 II
题目描述
给定一个整数数组 stones，表示一堆石头的重量。每一回合，可以选择任意两块石头，将它们粉碎。如果两块石头的重量分别为 x 和 y（x <= y），则：
-
如果
x == y，则两块石头都被完全粉碎； -
如果
x != y，则重量为x的石头完全粉碎，重量为y的石头的新重量为y - x。
最终，最多只会剩下一块石头。任务是返回这块石头的最小可能重量。如果没有石头剩下，则返回 0。
示例 1：
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
示例 2：
输入：stones = [31,26,33,21,40]
思路步骤
-
计算总和：首先计算所有石头的总重量。
-
确定目标：由于我们需要找到最后剩下的石头的最小可能重量，我们可以将问题转化为找到一个子集，使得这个子集的总重量与总重量的一半尽可能接近。
-
初始化动态规划数组：创建一个长度为
总重量的一半 + 1的数组dp，用于存储从0到总重量的一半是否可以通过stones中的石头重量组合得到。 -
填充动态规划数组：遍历数组
stones，对于每个石头的重量stones[i]，从总重量的一半开始向下遍历dp数组，更新dp[j]的值。 -
计算结果：最后，返回
总重量 - 2 * dp[总重量的一半]，这将是最后剩下石头的最小可能重量。
代码实现
class Solution { public int lastStoneWeightII(int[] stones) { // 计算所有石头的总重量 int sum = 0; for (int num : stones) { sum += num; } // 目标是总重量的一半 int target = sum >> 1; // 初始化动态规划数组 int[] dp = new int[target + 1]; // 使用动态规划填充dp数组 for (int i = 0; i = stones[i]; j--) { // 更新dp[j]的值，取当前dp[j]与dp[j-stones[i]]+stones[i]的较大值 dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]); } } // 返回最后剩下石头的最小可能重量 return sum - 2 * dp[target]; }}时间复杂度
时间复杂度为 O(n*sum/2)，其中 n 是数组 stones 的长度，sum 是数组元素的总和。这是因为我们需要两层循环，外层循环遍历数组，内层循环从 target 开始向下遍历 dp 数组。
空间复杂度
空间复杂度为 O(sum/2)，这是因为我们使用了一个大小为 sum/2 + 1 的数组 dp 来存储中间结果。由于 sum 是数组元素的总和，这个值最多是数组中所有元素的和，因此空间复杂度与数组中元素的总和成正比。
文章持续跟新，可以微信搜一搜公众号 [ rain雨雨编程 ]，第一时间阅读，涉及数据分析，机器学习，Java编程，爬虫，实战项目等。
