arrays - 动态规划 : Number of moves to reduce the array to 1 number

Question

我正尝试使用动态规划表填充方法来解决优化问题，但我无法将问题分解为最优子结构。

问题是:

给定一个排序数组，从种子元素开始，在多少步后你可以将数组减少到只有一个元素。

1. 你可以删除除种子之外的数组元素，这被认为是 1 步，这减少了数组。
2. 您可以将小于种子的数组元素添加到种子中。这被认为是 1 步。
3. 您可以使用之前的方法添加到种子中，次数不限。
4. 种子可以“消耗”任何少于它的元素。这减少了数组。

例如，这是排序后的数组

3, 20, 50, 100, 400

第一个元素是种子。

第一个元素还不能消耗下一个更大的元素，所以我们需要添加它。根据限制，我们可以在 1 步内添加任何少于种子的东西。所以，假设我们加 2。

moves = 1
seed = seed + 2
5, 20, 50, 100, 400

仍然seed不能消耗下一个元素，所以让我们加4

moves = 2
seed = seed + 4
9, 20, 50, 100, 400

moves = 3
seed = seed + 8
17, 20, 50, 100, 400

moves = 4
seed = seed + 16
33, 20, 50, 100, 400

现在种子可以“消耗”下一个元素所以减少的数组变成了

53 (33 + 20) , 50, 100 , 400

53可以消耗50变成103

103, 100, 400

103可以消耗100变成203

203, 400

203是种子，不能消耗400所以

moves = 5
seed = seed + 202
405, 400

现在可以消费变成805

我们也可以简单地删除 400，这将被计为 1 步。

总步数 = 5

但还有另一种解决方案，即从数组中删除所有元素(20、50、100、400)，这将需要 4 步。

所以在这种情况下，最小移动次数是 4。

尝试从动态规划的角度来思考它，我可以看到在每一步我们都有 2 个选择，是消耗元素还是移除元素。似乎要考虑的路径总数是所有 2^n 条路径。

但我未能将其分解为重叠的子问题或最佳子结构，甚至无法定义递归关系。

这里动态规划是正确的方法吗？

一些观察:

1. 当我们必须向种子添加一些东西时，最好的方法似乎是添加可能允许的最高值，即种子 - 1
2. 一旦我们决定删除一个元素，就意味着该元素后面的元素也将被删除。为什么，因为如果我们已经决定将多次添加到种子中对于当前元素是徒劳的，那么它对于下一个更大的元素也将适用。

Answer 1

您可以使用 (max{given array}+1)* array_size 时间和内存复杂度来解决它。

int dp[array_size][max{given array}+1]={INF} // initially all index holds infinity
int seed=array[seed_index];
int Max=max{given array}+1;
dp[0][seed]=0; 
for(int i=1;i<=n;i++){  // Consuming or removing ith element
   for(int j=1;j<=Max;j++){ // if the current seed value is j
       //Consider the removing case
       dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
       // Increasing seed value
        dp[i-1][min(Max,j+(j-1))]=min(dp[i-1][min(Max,j+(j-1))],dp[i-1][j]+1);
       // Consider the consuming case
       if(j>array[i]){
          dp[i][min(Max,j+array[i])]=min(dp[i-1][j],dp[i][min(Max,j+array[i])]);  // If j is the current seed value and you want to consume ith element then  after consuming the ith element the seed will be j+array[i] but if it is greater than Max we can take upto max . Because for consuming the maximum value we need only the Max value. 
       }
   }
}

// Now check the smallest possible value for the latest number.
result = INF;
for(int i=0;i<=Max;i++)result=min(result,dp[n][i]);

这里 dp[i][j] 表示将数组减少到第 i 个值的结果，在减少到第 i 个值后，种子将是 j 。并且 dp[i][j] 将保存移动数以减少到第 i 个值到 1 个具有种子值 j 的元素。

在消费情况下:
如果 j 是当前的种子值，并且你想消耗第 i 个元素，那么在消耗第 i 个元素之后，种子将为 j+array[i] 但如果它大于 Max 我们可以取到 Max 。因为要消耗最大值，我们只需要 max{given array} 的最大值+1。

递归方法:

int dp[array_size][max{given array}+1]={-1} // initially all index holds -1
int Max=max{givenarray}+1;

int DP(int seed,int index){
   if(index==n+1)return 0;
   if(dp[seed][index]!=-1)return dp[seed][index];// previously calculated
   int res=inf;
   // By removing
    res=DP(seed,i+1)+1;
   //Increasing seed
   if(seed<Max)
      res=min(res,1+DP(min(Max,seed+seed-1),index));
   // By consuming
   if(seed>array[i])
      res=min(res,DP(seed+array[i],i+1));
   dp[seed][index]=res;
  return res;
}