AlgoPressAppearance
1049-最后一块石头的重量II
https://leetcode.cn/problems/last-stone-weight-ii
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：
输入：stones = [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]，这就是最优值。
示例 2：
输入：stones = [31,26,33,21,40]
输出：5
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 100
思路
将问题转化为01背包问题，计算一半的重量，转化问题为有最大一半重量的背包，看能装入最大多少重量的石头。 这样最后计算的结果为 sum - 背包里的重量 - 背包里的重量
代码
csharp
public class Solution {
public int LastStoneWeightII(int[] stones) {
int maxWeight = 0;
for(int i=0; i<stones.Length; i++){
maxWeight+=stones[i];
}
int target = maxWeight / 2;
int[] dp = new int[target+1];
for(int i=0; i<stones.Length; i++){
for(int j = target; j>=0; j--){
if(j >= stones[i]){
dp[j] = Math.Max(dp[j],dp[j-stones[i]] + stones[i]);
}
}
}
return maxWeight - dp[target] - dp[target];
}
}
复习:二维dp
csharp
public class Solution {
public int LastStoneWeightII(int[] stones) {
int sum = 0;
for(int i=0; i<stones.Length; i++){
sum+=stones[i];
}
int target = sum / 2;
//问题转化为容量为 target的背包能最多装多少石头
//dp[i,j] 表示从0-i中选取n个数能凑成最大的重量
int[,] dp = new int[stones.Length,target+1];
//初始化
for(int i=0; i<=target; i++){
if(stones[0] <= i){
dp[0,i] = stones[0]; //只能选择一个石头的时，能放进去的那个就是价值
}
}
for(int i=1; i<stones.Length; i++){
for(int j=0; j<=target; j++){
if(j >= stones[i]){
//选他或者不选他
dp[i,j] = Math.Max(dp[i-1,j],dp[i-1,j-stones[i]]+stones[i]);
}
else{
dp[i,j] = dp[i-1,j];
}
}
}
int bag = dp[stones.Length-1,target];
return sum - bag -bag ;
}
}
复习：一维dp 20220514
csharp
public class Solution {
public int LastStoneWeightII(int[] stones) {
//一维dp
int sum = 0;
for(int i=0; i<stones.Length; i++){
sum+=stones[i];
}
int target = sum / 2;
int[] dp = new int[target+1]; //dp[i]表示能够装入 i 最大的重量
for(int i=0; i<stones.Length; i++){
for(int j=target; j>=0; j--){
if(j>=stones[i]){
dp[j] = Math.Max(dp[j],dp[j-stones[i]] + stones[i]);
}
}
}
return sum - dp[target] - dp[target];
}
}
复习：20220515
csharp
public class Solution {
public int LastStoneWeightII(int[] stones) {
int sum = stones.Sum();
int target = sum / 2;
int[] dp = new int[target+1];
for(int i=0; i<stones.Length; i++){
for(int j=target; j>=0; j--){
if(j>=stones[i]){
dp[j] = Math.Max(dp[j],dp[j-stones[i]] + stones[i]);
}
}
}
return sum - dp[target] * 2;
}
}
复习:20220629
csharp
public class Solution {
public int LastStoneWeightII(int[] stones) {
//将问题转化为，把石头尽量分为两部分，是其中一部分尽量为和的一半，这样两边相抵消就是差值 sum - weight*2
//转化为01背包问题，背包总量为和的一半，然后看能转入最大的石头数
int sum = stones.Sum();
int target = sum / 2;
int[] dp = new int[target+1]; //设置dp数组，dp[j]表示放入石头的最大重量
for(int i=0; i<stones.Length; i++){ //遍历物品
for(int j=target; j>=0; j--){ //遍历背包
if(j >= stones[i]){
dp[j] = Math.Max(dp[j],dp[j-stones[i]]+stones[i]);
//Console.WriteLine("dp[{0}]={1}",j,dp[j]);
}
}
}
int weight = dp[target];
return sum - weight*2;
}
}