C ++中的Last Stone Weight II
假设我们有一个岩石集合，现在每个岩石都有一个正整数权重。在每个回合中，我们选择任意两个岩石并将它们粉碎在一起。如果宝石的权重为x和y，且x<=y。粉碎的结果将是-
如果x=y，则两块宝石都被完全破坏；
如果x！=y，则重量为x的石头将被完全破坏，重量为y的石头将具有新的重量yx。
最后，最多剩下1块石头。我们必须找到这种石头的最小重量（如果没有剩余的石头，则重量为0。）
因此，例如，如果输入类似于[2,7,4,1,8,1]，则输出将为1。这是因为如果粉碎(2,4)，则新数组将为[2，7,1,8,1]，将其粉碎(7,8)，新数组将为[2,1,1,1]，然后粉碎(2,1)，该数组将为[1,1，1]，然后粉碎(1,1)，因此只有1个。
为了解决这个问题，我们将遵循以下步骤-
n：=宝石阵列的大小，设置总计：=0
对于i，范围为0至n–1
总数：=总数+宝石[i]
要求：=总计/2
使数组dp的大小为req+1，并用假值填充它
dp[0]：=true，达到：=0
对于i，范围为0至n–1
dp[j]：=false（dp[j]和dp[j–stone[i]]）均为假时，否则为true
如果dp[j]为真，则达到：=达到和j的最大值
对于j：=req，当j–stone[i]>=0时，将j减1
总回报–（2*覆盖率）
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
int n = stones.size();
int total = 0;
for(int i = 0; i < n; i++){
total += stones[i];
}
int req = total / 2;
vector <bool> dp(req + 1, false);
dp[0] = true;
int reach = 0;
for(int i = 0; i < n; i++){
for(int j = req; j - stones[i] >= 0; j--){
dp[j] = dp[j] || dp[j - stones[i]];
if(dp[j]) reach = max(reach, j);
}
}
return total - (2 * reach);
}
};
main(){
vector<int> v = {2,7,4,1,8,1};
Solution ob;
cout << (ob.lastStoneWeightII(v));
}输入值
[2,7,4,1,8,1]
输出结果
1