java - 在递归中求和

Question

递归求和:是否总是产生 StackOverflow 错误？

public final static float getAlpha(int t, int i, int N, float[] P, float[][] B, float[][] A, int[] O)
{
    float alpha;
    if (t==1)
    {
        alpha = P[i] * B[i][O[0] - 1];
    }
    else
    {
        float sum = 0;
        int k;
        for (k=0; k < N; k++){
            sum = sum + (getAlpha(t-1, k, N, P, B, A, O) * A[k][i]);
        }
        alpha = sum * B[i][O[0] - 1];
    }
    return alpha;
}

我收到该行的错误:

sum = sum + (getAlpha(t-1, k, N, P, B, A, O) * A[k][i]);

有什么创造性的解决方案吗？

Answer 1

我建议使用动态规划方法。这样就不会计算第二次值，您也不必担心堆栈溢出。

创建一个 t by N 数组。

所以 Array[i][0] = P[i] * B[i][O[0] - 1]

从这里您可以对前一行的所有元素求和，然后乘以 A[k][i] 和 B[i][O[0] - 1]，其中 k 是上一列所在行的索引，i 是当前列所在行的索引。

对于最终结果，您需要使用最初调用它时使用的 i 的值。

这样你只做 2*t 乘法和 t*N*N 求和。比你现在做的要少得多。

如果您在实际实现方面需要帮助，您应该查阅 veterbi 算法。这很相似。