对于这个,有什么比蛮力更好的解决方案？

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）以进行 make [0,0,0,0...]，方法是减少所有内容或减少单个项目。这当然是同一个问题，但步骤相反。

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

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

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

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

A [i]是所有全局减量的成本。- A[i] * (Ni)是所有不环绕的高位元素的成本减少，成本i*(UPPER_BOUND+1-A[i])是所有不环绕的元素增加的成本从0环绕到UPPER_BOUND。

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