代码随想录算法训练营 Day36 代码随想录算法训练营第 36 天 |LeetCode1049. 最后一块石头的重量 II LeetCode 494. 目标和 LeetCode 474.一和零 目录 代码随想录算法训练营前言LeetCode1049. 最后一块石头的重量 IILeetCode 494. 目标和 LeetCode 474.一和零一、LeetCode1049. 最后一块

题1： 指路：1049. 最后一块石头的重量 II - 力扣（LeetCode） 思路与代码： 本题中，我们要让剩下的石头重量尽可能小，那么每次就要尽可能找重量相等或最相近的两个石头，如果我们把两个石头分别放入两个数组内，再继续按照重量找尽量相等的石头，此时我们发现，两个数组内的元素和趋于相等，也就是两个数组的元素和尽量等于原数组和的一半，像极了第二题 分割等和子集。与之不同的是需要返回剩下

算法题 Leetcode 1049.最后一块石头的重量II 题目链接:1049.最后一块石头的重量II  大佬视频讲解：最后一块石头的重量II视频讲解  个人思路 和昨天的分割等和子集有些相像，这道题也是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。 解法 动态规划 动规五部曲： 本题物品的重量为stones[i]，物品的价值也

LeetCode1049. 最后一块石头的重量 II 这道题难点在于如何转换成背包问题，其实和上一题和相等子集合基本一样，尽量把石头分成两个重量相等的集合，那么在碰撞之后和就是最小的，石头的重量也可以当作石头的价值，代码也基本一样，就是最后的返回值是返回最小的差值，除法是向下取整，所以sum-dp[target]>dp[target]。 代码如下：时间复杂度O(m*n)；空间复杂度O(m)。

解题思路： 把石头堆分割成差不多的两堆，使得两堆差值最小 dp数组的含义： dp[j]:背包容量为j的背包最大重量(价值)为dp[j] dp[j] = max(dp[j],dp[j-stones[i]] + stones[i]) 初始化：（dp数组的大小根据题目进行定义） dp[0] = 0 其余非0下标也初始化为0 遍历顺序： 先物品再背包（倒序） 代码实现：求出dp[tar