动态编程-部分元素之和
假设我们有一个这样的数字数组-
const arr = [1, 2, 3, 4, 5];
每次减少一个元素，该数组可以像这样分离出来-
[1, 2, 3, 4, 5] [2, 3, 4, 5] [3, 4, 5] [4, 5] [5] []
我们需要编写一个包含一个这样的数组的JavaScript函数。该函数应以上述相同的方式将数组分开。
然后，该函数应构造一个包含这些部分各自总和的数组并返回该数组。
因此，对于此数组，输出应类似于-
const output = [15, 14, 12, 9, 5 0];
我们将使用动态编程来解决此问题。我们将首先计算O(n)时间内完整数组的总和，最终将成为数组的第一个元素。然后在另一个迭代中，我们将继续减去相应的元素以获得输出数组元素。这样，我们可以在O(n)时间和O(1)空间中解决此问题。
示例
const arr = [1, 2, 3, 4, 5];
const sumArray = (arr = []) => arr.reduce((a, b) => a + b, 0);
const partialSum = (arr = []) => {
let sum = sumArray(arr);
const res = [sum];
for(let i = 0;
i < arr.length; i++){
const el = arr[i];
sum -= el;
res.push(sum);
};
return res;
};
console.log(partialSum(arr));输出结果
这将产生以下输出-
[ 15, 14, 12, 9, 5, 0 ]