問題是通過重復該程序M次來找到長度為N的陣列的前綴和。例如
Example N=3
M=4
array = 1 2 3
output = 1 6 21
Explanation:
Step 1 prefix Sum = 1 3 6
Step 2 prefix sum = 1 4 10
Step 3 prefix sum = 1 5 15
Step 4(M) prefix sum = 1 6 21
Example 2:
N=5
M=3
array = 1 2 3 4 5
output = 1 5 15 35 70
我無法解決問題并不斷超出石灰限制。我使用動態編程在 O(NM) 時間內解決它。我環顧四周，找到了以下通用數學解決方案，但我仍然無法解決它，因為我的數學不是很好理解它。有人可以以更好的時間復雜度解決它嗎？
https://math.stackexchange.com/questions/234304/sum-of-the-sum-of-the-sum-of-the-first-n-natural-numbers
uj5u.com熱心網友回復：
提示：3, 4, 5和6, 10, 15是帕斯卡三角形的對角線部分。
JavaScript代碼：
function f(n, m) {
const result = [1];
for (let i = 1; i < n; i )
result.push(result[i-1] * (m i 1) / i);
return result;
}
console.log(JSON.stringify(f(3, 4)));
console.log(JSON.stringify(f(5, 3)));轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/489542.html
下一篇：識別演算法的基本操作