有多个表单查询
Q(n,m) = (nC1*mC1) + (nC2*mC2) + (nC3*mC3) ... (nCk*mCk) where k=min(n,m)
如何在 O(1) 时间复杂度内找到 Q(n,m) 的值。
我尝试预先计算 ncr[N][N] 矩阵和 dp[N][N][N] 其中 dp[n][m][min(n,m)] = Q(n ,m).
此预计算需要 O(N^3) 时间，现在可以在 O(1) 时间内回答查询。但我正在寻找一种预计算不应花费更多 O(N^2) 时间的方法。
最佳答案
从 C(n,0)*C(m,0) 开始的解决方案看起来很简单
Q0(n,m) = C(n+m, m)
因此对于您的公式只需减去 1
Q(n,m) = C(n+m, m) - 1
例子:n=9, m=5
帕斯卡三角形的第 9 行和第 5 行的点积是
1 9 36 84 126 126 84 36 9 1
1 5 10 10 5 1
1 + 45 + 360 + 840 + 630 + 126 = 2002 = C(14,5)
可以从Q(n,1)开始用数学归纳法证明，但是表达式比较长。
我发现了这个命题的一个真正奇妙的证明，即这个边距太窄而无法容纳 © Fermat ;)
关于algorithm - O(1) 时间复杂度的以下 ncr 系列的总和，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53200474/