LeetCode-GoLast Stone Weight II 的 01 背包转化——一维 DP 实现与源码解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇以 LeetCode-Go 中 LeetCode 1049 题Last Stone Weight II最后一块石头的重量 II的题解文档为主体完整继承其题目描述、约束条件与解题思路并结合仓库中的 Go 实现源码、测试用例展开源码级解析。读完后你将掌握如何把石头对撞求最小剩余重量这一贪心直觉失效的场景转化为 01 背包问题以及如何用一维数组 DP 以O(n * sum/2)时间、O(sum/2)空间完成求解。题目陈述英文原题We have a collection of rocks, each rock has a positive integer weight.Each turn, we chooseany two rocksand smash them together. Suppose the stones have weightsxandywithx y. The result of this smash is:Ifx y, both stones are totally destroyed;Ifx ! y, the stone of weightxis totally destroyed, and the stone of weightyhas new weighty-x.At the end, there is at most 1 stone left. Return thesmallest possibleweight of this stone (the weight is 0 if there are no stones left.)题目大意有一堆石头每块石头的重量都是正整数。每一回合从中选出任意两块石头然后将它们一起粉碎。假设石头的重量分别为 x 和 y且x y。那么粉碎的可能结果如下如果x y那么两块石头都会被完全粉碎如果x ! y那么重量为 x 的石头将会完全粉碎而重量为 y 的石头新重量为y-x。最后最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下就返回 0。示例原文档给出的 Example 1 及其推演过程如下完整保留以便理解碰撞顺序可任意选择、目标是全局最优这一要点Input: [2,7,4,1,8,1] Output: 1 Explanation: We can combine 2 and 4 to get 2 so the array converts to [2,7,1,8,1] then, we can combine 7 and 8 to get 1 so the array converts to [2,1,1,1] then, we can combine 2 and 1 to get 1 so the array converts to [1,1,1] then, we can combine 1 and 1 to get 0 so the array converts to [1] then thats the optimal value.即先 2 撞 4 得 2再 7 撞 8 得 1再 2 撞 1 得 1最后 1 撞 1 抵消剩余重量 1。约束条件原文档同时保留了英文与中文两处提示需注意二者对单块石头重量的上界描述不一致1 stones.length 30英文版1 stones[i] 100中文版1 stones[i] 1000这一不一致直接决定了背包容量sum/2的上限英文版下sum 3000中文版下sum 30000但两种取值规模对本文所述 DP 方案都完全可行属于典型的总重量可枚举背包规模。核心思路从石头碰撞到 01 背包原文档解题思路部分给出的转化论证是本题的灵魂完整继承如下给出一个数组数组里面的元素代表的是石头的重量。现在要求两个石头对碰如果重量相同两个石头都消失如果一个重一个轻剩下的石头是两者的差值。问经过这样的多次碰撞以后能剩下的石头的重量最轻是多少由于两两石头要发生碰撞所以可以将整个数组可以分为两部分如果这两部分的石头重量总和相差不大那么经过若干次碰撞以后剩下的石头重量一定是最小的。现在就需要找到这样两堆总重量差不多的两堆石头。这个问题就可以转化为 01 背包问题。从数组中找到sum/2重量的石头集合如果一半能尽量达到sum/2那么另外一半和sum/2的差是最小的最好的情况就是两堆石头的重量都是sum/2那么两两石头对碰以后最后都能消失。01 背包的经典模板可以参考第 416 题。对这一论证可以补充三点理解使其在数学上更完整为什么是分两堆任意一次x撞yx y等价于给y标上负号、把x并入y的累积反复碰撞的最终结果实际上等于给每块石头独立地赋予或-号后求代数和的绝对值。因此问题等价于给所有石头分成两堆正号堆与负号堆使两堆重量差|sum - 2 * w1|最小其中w1是正号堆的总重。为什么背包容量取sum/2设两堆重量为w1 w2则w1 w2 sum且w2 - w1 sum - 2*w1。剩余重量w2 - w1随w1单调递减所以只要让较小一堆的重量w1在不超过sum/2的前提下尽量大最终剩余重量就最小。最优剩余的下界若存在恰好sum/2的划分且sum为偶数则答案为 0否则答案为sum - 2*dp[sum/2]这正是仓库源码最后一行直接输出的表达式。原文档指出 01 背包经典模板可参考第 416 题Partition Equal Subset Sum仓库中对应实现见 416 题源码。两题结构几乎同构差异仅在于状态含义416 题用布尔 DP 判断是否能恰好装满sum/2而 1049 题需要不超过sum/2时能装到的最大重量因此 1049 题的状态必须记录最大可达重量而非可达性。源码实现解析仓库中的完整实现位于 1049. Last Stone Weight II.go全文仅 30 行逐段拆解如下。状态定义与一维化n, C, dp : len(stones), sum/2, make([]int, sum/21)这里采用一维dp数组dp[j]表示在容量上限为j的前提下从石头中选取若干块能凑出的最大总重量。相比二维dp[i][j]前 i 块石头、容量 j一维化把物品维度折叠进外层循环是 01 背包的标准压缩手法空间从O(n * sum)降为O(sum)。首块石头的初始化for i : 0; i C; i { if stones[0] i { dp[i] stones[0] } else { dp[i] 0 } }dp零值初始化后容量i若容得下stones[0]则最大可达重量为stones[0]否则为 0。这一写法与 416 题源码 中dp[i] (nums[0] i)的布尔初始化完全对应——1049 题把是否可达放宽成了可达重量值。01 背包转移倒序遍历的关键for i : 1; i n; i { for j : C; j stones[i]; j-- { dp[j] max(dp[j], dp[j-stones[i]]stones[i]) } }状态转移方程为dp[j] max(dp[j], dp[j - stones[i]] stones[i])对应二维形式F(i, j) max(F(i-1, j), F(i-1, j-w[i]) w[i])不选第 i 块则保持dp[j]选第 i 块则在dp[j-stones[i]]的基础上加上stones[i]。内层循环j必须从C倒序减到stones[i]这是 01 背包一维化的正确性核心倒序保证更新dp[j]时读取的dp[j-stones[i]]仍是只用了前 i-1 块石头的旧值从而每块石头至多被选一次若正序遍历旧状态会被新状态污染等价于完全背包同一块石头可反复使用对本题会得到错误答案。注意转移中有一个隐含的边界保护当stones[i] C时内层循环条件j stones[i]一开始就不成立该石头被自动跳过不会越界。从源码结构看自实现max函数func max(a int, b int) int { if a b { return a } return b }根 go.mod 声明模块语言版本为go 1.19而 Go 的内建max函数要到 Go 1.21 才引入因此本题在包级定义了自己的max。这也解释了为何函数体直接内联在 题目解法文件 中而非依赖标准库。答案输出return sum - 2*dp[C]dp[C]就是不超过sum/2能凑出的最大重量w1另一堆重量为sum - w1二者之差即最小剩余重量。当dp[C] sum/2时表达式自然输出 0与题目如果没有石头剩下就返回 0的要求吻合。测试用例与运行方式仓库为每题配备Test_ProblemXXXX测试函数1049 题测试文件 覆盖了三组用例输入期望输出覆盖场景[2, 7, 4, 1, 8, 1]1文档 Example 1 的标准样例[21, 26, 31, 33, 40]5无sum/2整除划分的较难样例sum151dp[75]73151-2*735[1, 2]1最小长度边界两块石头直接相减测试函数以表驱动方式构造question1049para1049输入 ans1049期望切片循环调用lastStoneWeightII并打印实际输出与期望值对照核验。可在仓库根目录运行以下命令单独执行本题测试go test -v -run Test_Problem1049 ./leetcode/...仓库根目录的 gotest.sh 则演示了全量运行方式go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本通过 Go 1.10 对多包一次性-coverprofile的能力生成单一合法的覆盖率文件产出根目录的 coverage.txt保证仓库宣称的 100% 测试覆盖率统计口径统一。复杂度分析设n len(stones)S sum(stones)时间复杂度外层遍历 n 块石头内层背包容量最多到S/2故为O(n * S/2) O(n * S)。在英文版约束stones[i] 100下S 3000总运算量不超过 9 万次量级即使按中文版约束stones[i] 1000S 30000运算量也在千万次以内远低于暴力模拟碰撞的指数级搜索空间。空间复杂度一维dp数组长度为S/2 1即O(S)。对比原文档给出的思路——找到两堆总重量差不多的石头集合——源码实现正是该思路的忠实落地容量C sum/2的 01 背包求出w1的上确界dp[C]一步sum - 2*dp[C]得到答案全程无需回溯具体的碰撞顺序。小结与延伸本题的完整题解链路在仓库中由三个文件构成可对照阅读题目与思路文档题目陈述、约束与碰撞 → 分堆 → 01 背包的转化论证Go 解法30 行内完成一维 01 背包倒序转移 sum - 2*dp[C]收尾测试文件覆盖标准样例、一般样例与最小规模边界。掌握本题的关键收获有二其一凡正负号分配求最小差值型问题石子、拆分、抵消类优先检验能否套入 01 背包其二当答案需要不超过容量时的最优值而非能否恰好达到时应把 416 题式的布尔可达 DP 升级为 1049 题式的重量求和 DP状态含义从bool变为int转移从||变为max其余一维化与倒序遍历的骨架保持不变。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
