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

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 where i=0 or A[i] > A[i-1].

对于每个这样的位置，很容易计算在 A[i] 达到 0 和 then[=54= 之前递减所有内容所产生的成本] 一个一个递减。这很容易，因为我们知道索引 < i 的所有内容都会环绕，而索引 >= 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[ 的所有元素增加的成本=46=].

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

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

What is a better solution than brute force for this?

algorithm

performance

brute-force