algorithm - 有什么比蛮力更好的解决方案呢？

Question

给定 [0-5] 之间的有限正整数序列让我们说 [0,3,1,5,2,4,4,4] 和一个起始序列 [0,0,0,0,0,0,0,0]。我们现在想要通过执行逐步操作从起始序列构建我们给定的序列。在一步中，我们可以将起始序列中的所有数字增加 1，或者仅将此序列中的一个索引增加 1。在这种情况下，一旦我们增加 5，它就会变成 0。

找到需要最少步骤的解决方案的最有效方法是什么？这个解决方案当然也适用于其他输入(长度+上限)。对于起始序列，我们可以假设每个索引始终为 0。

蛮力方法可能看起来像这样。

int upperBound = 5;
int[] endSequence = {0,3,1,5,2,4,4,4};
int currentBestSteps = Integer.MAX_VALUE;
int currentTimesIncreaseAll = 0;

for(int start = 0;start <= upperBound;start++){ //how many times to increase all
  //counter how many steps required total, starting with start amount of steps
  //since we increase all values 'start' times  
  int counterSteps = start; 

  //go through all end values and calc how many steps required  
  for(int end:endSequence){ 
    if(start <= end){
      counterSteps += end-start;
    }else{
      counterSteps += end+upperBound+1-start;
    }
  }

  System.out.println("solution: increase all "+start+
                     " times, total steps: "+counterSteps);

  if(counterSteps < currentBestSteps){
    currentBestSteps = counterSteps;
    currentTimesIncreaseAll = start;
  }
}
System.out.println("best solution: increase all "+currentTimesIncreaseAll+
                   " times, total steps: "+currentBestSteps);

结果:

solution: increase all 0 times, total steps: 23
solution: increase all 1 times, total steps: 22
solution: increase all 2 times, total steps: 21
solution: increase all 3 times, total steps: 20
solution: increase all 4 times, total steps: 19
solution: increase all 5 times, total steps: 30
best solution: increase all 4 times, total steps: 19

Answer 1

我将提供一种方法来递减目标原始数组(称之为A)，使[0,0,0,0...]，通过递减所有内容或递减单个项目。这当然是同一个问题，只是步骤相反。

首先，计算将所有元素逐一递减的成本。将此成本称为 CMAX 并将数组的长度称为 N。 CMAX = sum_for_all_i(A[i])

然后对数组进行排序，找到i中i=0或者A[i] > A[i-1]的每个位置.

对于每个这样的位置，很容易计算出递减所有内容直到 A[i] 达到 0，然后然后逐个递减所产生的成本。这很容易，因为我们知道索引 的所有内容都会回绕，而索引 >= i 的所有内容都不会。所以:

COST(i) = CMAX + A[i] - A[i] * (N-i) + i*(UPPER_BOUND+1-A[i])

A[i] 是所有全局递减的成本。 - A[i] * (N-i) 是所有不环绕的高元素的成本降低，而成本 i*(UPPER_BOUND+1-A[i] ) 是从 0 到 UPPER_BOUND 的所有元素增加的成本。

您找到的最低COST(包括CMAX)就是您的答案。总复杂度为 O(N log N)，主要由排序决定。如果上限保证很小，那么您可以对其使用计数排序并得到 O(N+k)