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