2

我被要求编写一个递归函数，该函数将计算沿具有 n × n 方格的网格边缘的单调格子路径的加泰罗尼亚数，这些格子路径不会超过对角线（图片）

我不允许用于-循环，只有递归调用......这就是我所做的：

public long C(int n) {
    if (n == 1)
        return 0;
    return C(n, 0, 0);
}

private long C(int n, int i, int j) {

    // CAN MOVE UP & RIGHT
    if (j - i > 0 && j + 1 <= n)
        return paths(n, i + 1, j) + paths(n, i, j + 1);
    // CAN MOVE UP
    else if (j - i > 0)
        return paths(n, i + 1, j);
    // CAN MOVE RIGHT
    else if (j + 1 <= n)
        return paths(n, i, j + 1);
    // CAN'T MOVE
    else
        return 1;
}

我不知道这段代码是否最好，但它可以工作......我想将此函数转换为 Memoized 函数。但我不明白它如何以及为什么它会使功能更高效。我理解为什么记忆中的斐波那契更有效，但是在这里我总是必须到达路径的末尾然后返回 1 或 0 那么如果我将 1 / 0 存储在一个数组中有什么关系呢？

感谢您的任何帮助

4

2 回答 2

3

但我无法理解 [...] 为什么它会使功能更高效。

看图，图片从1开始编号，左下角(x,y)坐标，可以看到图片2,3,4,5,6,7,8,10,12都经过点.(0,0)(3,1)

路径来自(3,1)：

  • (3,1) → (4,1) ↑ (4,2) ↑ (4,3) ↑ (4,4)
    • 图二、四、五
  • (3,1) ↑ (3,2) → (4,2) ↑ (4,3) ↑ (4,4)
    • 图 3、6、8
  • (3,1) ↑ (3,2) ↑ (3,3) → (4,3) ↑ (4,4)
    • 图 7、10、12

如您所见，您多次 (3) 次在同一条路径上行走。如果您可以缓存（记忆）从到最后有 3 条路径的事实，那么(3,1)您将节省时间。

随着网格变得更大，节省的时间也会增加。

加泰罗尼亚数字 4x4 网格示例

因此，您所做的是，第一次到达某个点时，您使用递归计算结果，就像您已经做的那样，然后保存该点的数字，当再次到达该点时，您只需使用缓存的值：

public static long paths(int n) {
    if (n == 1)
        return 0;
    return paths(n, 0, 0, new long[n][n]);
}
private static long paths(int n, int y, int x, long[][] cache) {
    long result = cache[y][x];
    if (result == 0) {
        if (y < x && x < n) // CAN MOVE UP & RIGHT
            result = paths(n, y + 1, x, cache) + paths(n, y, x + 1, cache);
        else if (y < x) // CAN MOVE UP
            result = paths(n, y + 1, x, cache);
        else if (x < n) // CAN MOVE RIGHT
            result = paths(n, y, x + 1, cache);
        else // CAN'T MOVE
            result = 1;
        cache[y][x] = result;
    }
    return result;
}
于 2015-12-12T20:05:45.757 回答
1

好像你知道什么是记忆。基本上，你所做的只是创建一个表memo，一旦你到达它就会存储一个值，这样你就不必再次在递归中计算它。类似于为什么fibonacci(5)不需要递归来查找的东西fibonacci(3)，如果我们已经计算过，比如说fibonacci(6)，因为我们已经记住了它。我希望你能明白。这是代码，以同样的精神记忆。安德里亚的问题有很好的视觉理解。

long[][]memo;  //Memo table

public long C(int n)
{
    if (n == 1)
        return 0;

    memo=new int[n+1][n+1]; //Increase to n+1 and won't crash!

    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            memo[j][i]=-1;

    return C(n, 0, 0, memo);
}

private long C(int n, int i, int j, it) {

    // CAN MOVE UP & RIGHT
    if (j - i > 0 && j + 1 <= n)
    {
        if(memo[i+1][j]==-1)
            memo[i+1][j]=paths(n, i + 1, j);

        if(memo[i][j+1]==-1)
            memo[i][j+1]=paths(n, i, j + 1);

        return memo[i+1][j]+memo[i][j+1];
    }
    // CAN MOVE UP
    else if (j - i > 0)
    {
        if(memo[i+1][j]==-1)
            memo[i+1][j]=paths(n, i + 1, j);
        return memo[i+1][j];
    }
    // CAN MOVE RIGHT
    else if (j + 1 <= n)
    {
        if(memo[i][j+1]==-1)
            memo[i][j+1]=paths(n, i, j + 1);
        return memo[i][j+1];
    }
    // CAN'T MOVE
    else
        return 1;
}
于 2015-12-12T20:02:26.333 回答