文件名称：leetcode伪代码-leetcode:leetcode
文件大小：8KB
文件格式：ZIP
更新时间：2024-07-20 13:45:52
系统开源
leetcode伪代码解：1049.最后的石重II 初步分析 让我们从一些观察开始。 让n表示石头的数量。 我们不需要区分x == y的情况：如果我们允许0作为差异，则输出（最终数字）保持不变。 输出总是一些权重的总和减去所有其他权重：如果输入是[s_1, s_2, ..., s_n ] ，输出总是可以被公式化为 ，其中每个系数c_i是+1或-1 . 每个系数组合对应于一系列碎石（保持非负yx差异），使得输出为 。 所以这实际上是 的优化版本，已知为 NP-hard。 伪多项式解 由于权0..100之间，因此使用动态规划技术有一个有效的解决方案。 如果值i可以是前(j+1)数字的确切输出，则让我们有一个二维数组D[j][i]信号True ( T )，否则为空 ( False )。 填充D[0][i]是微不足道的： D[0][s_1] := True并且该行的其余部分是False 。 对于j>0 ，我们可以使用前(j-1)行和新数字x （第(j+1)个数字， s_(j+1) ）： D[j][i] ：= True恰好如果D[j-1][i+x]或D[j-1][abs(ix)] 。 因此，对于
【文件预览】：
leetcode-master
----src()
--------Makefile(53B)
--------last-stone-weight-ii.cc(3KB)
--------include()
----img()
--------math2.svg(7KB)
--------math1.svg(7KB)
----README.md(3KB)