假设我们有一个岩石集合,现在每个岩石都有一个正整数权重。在每个回合中,我们选择任意两个岩石并将它们粉碎在一起。如果宝石的权重为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