c# - 使用巨大的二维数组递归获取最大路径和

Question

我必须获得二维数组的最大路径和。
我可以设法获取最多 40 行，但函数之后不返回任何值。
有人能帮我吗？

private int GetTotal(int row, int column, int[,] triangle)
{
    if (row == 0) return triangle[row, column];

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

    return Math.Max(left, right);
} 

Answer 1

您正在观察算法的指数运行时间。该算法的运行时间为 O(2^rows) - 这是一个相当大的数字。

考虑将您的代码转换为 Dynamic Programming解决方案，这基本上是实现此类递归的有效方法，无需两次计算某些值(代码中就是这种情况)。

最简单的方法是自上而下的动态规划，也称为 "memorization" 。
只需添加一个字典，我们称之为缓存，并在函数的开头 - 检查(行，列)是否在缓存中。如果是 - 只需返回已经计算出的值。
否则 - 计算值，并在返回之前 - 将其存储在缓存中。

这是基于您的代码的伪代码。它不会编译 - 但它应该演示当前的问题。

private long GetTotal(int row, int column, Pyramid pyramid, Dictionary<Pair<int,int>,long> cache)
{
    if (row == 0) return pyramid[row, column];
    //add a check if you already calculated for this row and column:
    Pair<int,int> p = new Pair<int,int>(row,column);
    if cache.ContainsKey(p) return cache.Get(p);

    int myValue = pyramid[row, column];
    long left = myValue + GetTotal(row - 1, column, pyramid, cache); //sending the dictionary as well...
    long right = myValue + GetTotal(row - 1, column + 1, pyramid, cache);

    long best = Math.Max(left, right);
    //before returning: store the just calculated value in the cache:
    cache.Add(p,best);
    return best;
}