将数组与init、元素、步骤相加

Question

嗨，我正在搜索一个快速的动态编程/公式解决方案。对于以下算法，例如：

init := 1

elements := 4

steps := 3

步骤1。[1,1,1,1]init被放置在每个索引中

步骤2。[1,2,3]索引i由前一个步骤索引0的和计算，直到包含步骤1的索引i，arraysize get递减1。

步骤3。[1,3]程序与步骤2相同，但以步骤2为基础。

最后的步骤CCD_ 7最后的步骤是对最后的步骤元素求和。

有比手动求和更快的方法吗？

样本代码：

long calc(int init,int elements,int steps){
int[] dp1 = new int[elements-1];
Arrays.fill(dp1, init);
int[] dp2 = new int[elements-1];
for(int i = 0; i < steps-1; i++){
for(int j = 0,cur = 0; j < elements-i-1; j++){
dp2[j] = cur = cur + dp1[j];
}
System.arraycopy(dp2,0,dp1,0,elements-i-1);
Arrays.fill(dp2, 0);
}
return Arrays.stream(Arrays.copyOf(dp1,elements-steps+1)).sum();
}

Answer 1

在不需要的地方进行了大量的复制和填充。这样试试吧。

static long myCalc(int init, int elements, int steps) {
if (steps > elements+1) {
System.out.println("Steps too large for # of elements");
return -1;
}
int[] dp1 = new int[elements - 1];
Arrays.fill(dp1, init);
int len = dp1.length;
for (int j = 0; j < steps - 1; j++) {
for (int i = 1; i < len; i++) {
dp1[i] = dp1[i - 1] + dp1[i];
}
len--;
}
return Arrays.stream(dp1).limit(len+1).sum();
}

增加了改进。对于每一步，都会少增加一个值。因此，调整for loop迭代以适应。

Answer 2

您可能需要查看Arrays.parallelPrefix方法。来自java文档：

使用提供的函数并行地累积给定数组的每个元素。例如，如果数组最初保持[2，1，0，3]，并且操作执行加法，则在返回时数组保持[2、3、3、6]。对于大型数组，并行前缀计算通常比顺序循环更有效。

所以下面这样的东西可能是你想要的：

long calc(int init,int elements,int steps){
int[] arr = new int[elements];
Arrays.fill(arr,init);
int[] curr = arr;
for (int i = 1; i < steps; i++){
Arrays.parallelPrefix(curr, Integer::sum);
curr = Arrays.copyOf(curr,curr.length-1);
System.out.println(Arrays.toString(curr)); // just to check the sub steps, remove if I get the discription of the steps right
}
return Arrays.stream(curr).sum();
}