动态规划递归

Question

我有一个用C#编写的递归方法/函数，它得到超过90行的2d数组的最大和路径。在大约25行时，递归停止。我试图克服这个问题，实现一个为斐波纳契所做的例子。结果是，仍然溢出，结果也是错误的。这就是我所做的，我感谢你们提出任何解决办法或建议。

编辑:仍然不能处理90行。

static long[,] cache = new long[1000, 1000];
private long GetTotal(int row, int column, long[,] triangle, long[,] cache)
{
    if (row == 0) return triangle[row, column];

    long myValue = triangle[row, column];
    long left = myValue + GetTotal(row - 1, column, triangle, cache);
    long right = myValue + GetTotal(row - 1, column + 1, triangle, cache);

    if (cache[row, column] !=0)   
    return cache[row, column];

    cache[row, column] = Math.Max(left, right);
    return cache[row, column]; 
} 

Answer 1

不应仅基于行进行缓存，而应同时基于行和列进行缓存。

您的代码现在存储一行的一个值，而不是每个行的多个值，以及每个(行、列)组合的一个值。

缓存的“键”应该是(行，列)。它可以用一个2D矩阵来解决--尽管它可能比一个Dictionary更具有扩展性(就重量而言)。