java将数组中的负索引转换为正索引(三项式三角形)
我试图找到三项式系数,我想避免在数组中使用负索引。在某些情况下,i或j将变为负值,并返回数组越界错误。是否可以将负索引中包含的数组镜像为正索引
下面是递归公式:Recursion Formula
我知道T(0, -1) = T(0, 1)
但是我该如何实现它呢
例如:
row 0: T(0, 0) = 1 , T(0, 1) = 0 ...
row 1: T(1, 0) = T(0, -1) + T(0, 0) + T(0, 1) , T(2, 0) ...
三项式系数T(n,k)
是(1+x+x^2)^n
展开式中x^(n+k)
的系数
三项式三角形(中间索引为0
,左边为负,右边为正):
注意:下面的代码从中间索引0
到右边遍历数组
public class ClassNameHere {
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
int k = Integer.parseInt(args[1]);
long[][] DP = new long[n + 1][k + 1];
DP[0][0] = 1;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= Math.min(i, k); j++) {
if (i == j || ((j == 0) && i < 2)) DP[i][j] = 1;
else if (j < -i) {
DP[i][j] = 0;
} else DP[i][j] = DP[i - 1][j];
}
}
System.out.println(DP[n][k]);
}
}
现在,我可以用我的代码获得从T(0, 0)
到T(1, 0)
的术语,但无法通过添加T(1,0) + T(1, 1) + T(1, 2)
继续从T(2, 0)
开始。当我试图实现DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j] + DP[i - 1][j + 1]
时,它再次返回ArrayIndexOutOfBoundsException
。。我认为执行上述声明有问题。关于如何继续下去有什么建议吗
# 1 楼答案
您可以按如下方式填充这样的数组:首先创建一个新的空数组,其高度为
n
,宽度为2n+1
,用零填充,并将上中点的第一个条目设置为1
,然后遍历行和列,并将其他条目设置为其上三个条目的总和:代码:
输出:
另见:Finding trinomial coefficients using dynamic programming