【动态规划】【背包问题】
Problem Link
有一堆石头,每块石头的重量都是正整数。
每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分别为 x
和 y
,且 x <= y
。那么粉碎的可能结果如下:
- 如果
x == y
,那么两块石头都会被完全粉碎; - 如果
x != y
,那么重量为x
的石头将会完全粉碎,而重量为y
的石头新重量为y-x
。
最后,最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下,就返回 0
。
Example:
示例:
输入:[2,7,4,1,8,1]
输出:1
解释:
组合 2 和 4,得到 2,所以数组转化为 [2,7,1,8,1],
组合 7 和 8,得到 1,所以数组转化为 [2,1,1,1],
组合 2 和 1,得到 1,所以数组转化为 [1,1,1],
组合 1 和 1,得到 0,所以数组转化为 [1],这就是最优值。
提示:
1 <= stones.length <= 30
1 <= stones[i] <= 1000
Analysis
- 由于石头拿走还能放回去,因此可以简单地把所有石头看作两堆
- 假设总重量为 sum, 则问题转化为背包问题:
- 如何使两堆石头总重量接近 sum / 2
定义:
dp[i]
背包容量限制为i
时能够装载的最大石块总重量curStone
存在最优解dp[i]
时需要考虑的下一块石块重量
$$\begin{equation}dp[i]=max\left{\begin{array}{lr}\text{dp[i],}&\quad\text{不拿取 curStone,}\text{dp[i-curStone] + curStone,} &\quad\text{拿取 curStone.}\end{array}\right.\end{equation} $$
具体可以参考背包问题理解
Solution 【动态规划】
执行用时 : 4 ms, 在Last Stone Weight II的Java提交中击败了78.67% 的用户
内存消耗 : 33.9 MB, 在Last Stone Weight II的Java提交中击败了100.00% 的用户
|
|
复杂度分析
时间:$O(M * N)$
空间:$O(M)$
M:石块总重;N:石块总数