Last Stone Weight II
欢迎关注
H寻梦人
公众号
You are given an array of integers stones where stones[i] is the weight of the ith stone.
We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
If x == y
, both stones are destroyed, and
If x != y
, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
At the end of the game, there is at most one stone left.
Return the smallest possible weight of the left stone. If there are no stones left, return 0.
Example1:
Input: stones = [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 that's the optimal value.
Example2:
Input: stones = [31,26,33,21,40]
Output: 5
Example3:
Input: stones = [1,2]
Output: 1
题目中文释义:
题解:
从上面题目的意思,其实我们可以转换一种角度来看待这个问题:
这个题目实质上其实就是,将所有的石子分为两堆,求两堆石子的最小绝对值的问题,最理想的答案是两堆石子一样多,但实际上可能会有偏差;假定所有的石子和为sum, 那么最终的一堆石子中必定有一堆的石子总和<=sum/2的,并且我们让其最大化。
因此,
这个问题就可以转为背包为sum/2的01背包问题, 假定其值为dp[cap]
那么,最终的结果为sum - 2*dp[cap]
证明:两堆石子的重量分别为x,y
结果为:|x-y|
假设x为其中较小的,那么结果为:y-x = (x+y)-2*x
因此,这问题就出来了,如下:
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int stone : stones) {
sum += stone;
}
int cap = sum / 2;
int[] dp = new int[cap +1];
for (int stone : stones) {
for (int i = cap; i >= stone; i--) {
dp[i] = Math.max(dp[i],dp[i-stone]+stone);
}
}
return sum - 2*dp[cap];
}