【文件属性】：
文件名称：leetcode伪代码-leetcode:leetcode
文件大小：8KB
文件格式：ZIP
更新时间：2021-06-30 19:59:12
系统开源
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)