【文件属性】:
文件名称: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)