将动态规划集成到递归解中

Question

我正在尝试将动态编程应用于以下问题：

“机器人位于m x n网格的左上角。机器人只能在任何时间点向下或向右移动。机器人正试图到达网格的右下角。有多少独特的路径？”

我有一个递归的解决方案，我认为效果很好。然而，它是缓慢的：

int uniquePaths(int m, int n)
    {
        if (m==1 || n==1)
        {
           return 1;
        }
        else 
        {
            return (uniquePaths(m,n-1)+uniquePaths(m-1,n));
        }
    }

我可以看到，如果我们能够保存uniquePath调用的输出将很有用，因为许多调用将不止一次完成。关于如何实现这一点，我有一个想法是创建一个m x n数组并将输出存储在其中。但是，这意味着我需要将数组输入到我的递归函数中，我认为对于这个问题，我只允许输入两个整数。有没有简单的方法来应用它？

Answer 1

不需要将数组作为函数参数输入。它可以是一个局部变量。

如果真的想使用递归函数，可以在uniquePaths中声明数组，然后调用另一个将使用该数组并进行计算的函数。

int uniquePaths_helper(int *grid, int m, int n, int i, int j);

int uniquePaths(int m, int n)
{
    int *grid = malloc(m * n * sizeof(int));
    int k;
    for (k = 0; k < m * n; ++k)
    {
        grid[k] = 0;
    }
    return uniquePaths_helper(grid, 0, 0, m, n);
}

int uniquePaths_helper(int *grid, int m, int n, int i, int j)
{
    if (grid[i * m + j] == 0)
    {
        if (i == n - 1 || j == n - 1)
        {
           grid[i * m + j] = 1;
        }
        else 
        {
            grid[i * m + j] = (
                uniquePaths_helper(grid,m,n, i+1, j)
                + uniquePaths_helper(grid,m,n, i, j+1)
            );
        }
    }
    return grid[i * m + j];
}

在之前的解决方案中，由于我们必须使用默认值初始化数组，因此会产生大量开销，然后在每次递归调用时，我们都需要检查值是否已存储在数组中或需要计算。

你可以走捷径。在网格的单元格中直接使用公式填充数组，而不是递归调用的参数。

公式是：grid[i*m j]==grid[（i 1）*m j]grid[i*m j 1]。

唯一棘手的部分是找出填充数组的顺序，这样这个公式就可以写成一个简单的赋值，用=替换=。

由于单元格中的值仅取决于具有更高i和j索引的值，我们可以简单地向后填充数组：

int uniquePaths(int m, int n)
{
    int *grid = malloc(m * n * sizeof(int));
    int i,j;

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

    for (i = n - 2; i >= 0; --i)
    {
        for (j = m - 2; j >= 0; --j)
        {
            grid[i * m + j] = grid[(i+1) * m + j] + grid[i * m + j+1];
        }
    }
    return grid[0];
}