使用动态规划查找三项式系数 [英] Finding trinomial coefficients using dynamic programming

问题描述

我正在尝试使用动态编程在Java中实现一个计算三项式系数的函数.我正在使用公式:

I'm trying to implement a function to calculate trinomial coefficient in Java using dynamic programming. I'm using the formula:

T(n,k)= 1 if n=0 and k=0
T(n,k)= 0 if k<-n or k>n 
T(n,k)=T(n-1,k-1)+T(n-1,k)+T(n-1,k+1)

我正在使用2D数组存储所有子问题的结果.但是，对于一个特定的 n 和 k 我得到的结果与正确答案相去甚远.这是我对方法的实现:

I'm using a 2D array to store results of all sub-problems. However, the result I get for a particular n and k is very far from the correct answer. Here is my implementation of the method:

public static long trinomial(int n, int k) {
    if (n == 0 && k == 0) return 1;
    if (k < -n || k > n) return 0;
    long[][] T = new long[n + 1][2 * n + 3];
    T[0][(2 * n + 3) / 2] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = -i; j <= i; j++) {
            T[i][j + n + 1] = T[i - 1][j + n] + T[i - 1][j + n + 1] + T[i - 1][
                    j + n + 2];
        }
    }
    if (k < 0) return T[n][k + n];
    else return T[n][k];
}

我得到 T(24,12)= 123286440 .但是，正确的答案是: 287134346 .我得到 T(3,3)= 6 .但是正确的答案是 1 .当我使用相同的方法在纸上计算 T(3,3)时，得到 T(3,3)= 1 ，但是在计算机中我得到了错误的答案.没有编译错误.

I get T(24,12) = 123286440. However, the correct answer is: 287134346. I get T(3,3) = 6. But the correct answer is 1. When I computed T(3,3) on a paper using the same method, I get T(3,3) = 1 but in computer I get the wrong answer. There are no compilation errors.

推荐答案

有一种更好的方法来实现该功能.三项式系数的系数三角形将是对称的，即T(n，k)= T(n，-k).因此，数组的列数可以与行数相同，即n + 1.而且，T(n，-k)也可以很容易地计算出来.这是实现:

There is a better way to implement the function. The triangle of coefficients for trinomial coefficients will be symmetrical, i.e., T(n,k)=T(n,-k). So, the no of columns for the array can be the same as row, i.e., n+1. And T(n,-k) can also be computed easily. Here is the implementation:

public static long trinomial(int n, int k) {
    if (n == 0 && k == 0) return 1;
    if (k < -n || k > n) return 0;
    long[][] T = new long[n + 1][n + 1];
    T[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) T[i][j] = T[i - 1][j] + 2 * T[i - 1][j + 1];
            else if (j == i) T[i][j] = T[i - 1][j - 1];
            else T[i][j] = T[i - 1][j - 1] + T[i - 1][j] + T[i - 1][j + 1];
        }
    }
    if (k < 0) return T[n][Math.abs(k)];
    else return T[n][k];
}

这篇关于使用动态规划查找三项式系数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！