寻找用于多次存储数组元素的特定总和的算法

Question

解决 Project Euler 的第 15 个问题，我正在努力解决算法实现中的最后一个问题。我错过了最后一步。我正在使用Java，但我只需要了解大概的意思。

假设我们有一个原始数组，比如 n = 20:

    long[] a = new long[20];

存储在数组中的数字直接决定了下一个数字序列（或本上下文中的路线）。为了更清楚，让我举个例子来说明我的意思：

假设我们有这样的订单：

    a[19] = ... ;
    a[18] = ... ;
    ...
    ...
    a[0] = ... ;

下一个序列元素应该如下所示：

   long[] b = new long[20]      

   for(int i = a.length - 1; i >= 0; i--){

    b[19] += a[i]; 

    }

    for(int i = a.length - 2 ; i >= 0; i--){

    b[18] += a[i]; 

    }
   ...

思路是序列数组 b 的顶部元素，根据上面的顺序，始终是数组 a 所有元素的总和。顶部元素下方的元素存储数组 a 的所有元素（顶部元素除外）。所以它基本上是以 descending/ascending 顺序对它们进行总结。因此 b[0] = a[0] 也是如此。下一个序列元素将是数组 b 的元素之和，依此类推...

问题是我需要能够对任意网格重复 n 次。

我该怎么做？

Answer 1

试试这个

long[] b = new long[20];
b[0] = a[0];

for(int i = 1; i < b.length; i++){
    b[i] = b[i-1] + a[i]; 
}

以上实用程序这个关系b(n) = b(n-1) + a(n)

寻找用于多次存储数组元素的特定总和的算法

Finding an algorithm for storing specific sums of elements of array multiple times

arrays

iteration

algorithm

storing-data