[算法]力扣刷题-动态规划 - 不同路径

题目：

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7 输出：28

示例 2：
输入：m = 3, n = 2
输出：3
解释： 从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

链接：https://leetcode-cn.com/leetbook/read/path-problems-in-dynamic-programming/rtwu06/

思路：

看到题目，基本确认是动态规划类问题。

我的思路是从终点向起点递归反推。首先确认状态转移方程：

因为每一步只能向下或向右移动，所以对于每一步的终点来说，只能是从上或从左移动而来。

因此起点走到点(x,y)的所有路径就是起点走到(x,y)上方点的所有路径加上起点走到(x,y)左方点的所有路径数量和。

即f(x,y) = f(x-1,y)+f(x,y-1)

当然有两种特殊情况：x为0或y为0，也即点在上边界一排或左边界一排时。
以上边界为例，上边界的点没有上方而来的路径，只有左方而来的路径。
因此y为0时公式为f(x,y) = f(x,y-1)，但继续推，（x,y-1）这个点同样只有左方而来的点，只有一条路径最终指向了起点。因此上边界的所有点可以直接认定为路径数为1。

左边界同理。

因此状态转移方程为：

f(x,y) = 
{
    f(x-1,y)+f(x,y-1), (x>0 && y>0)
    1,                 (x==0 || y==0)
}

以题目中给出的3*7大小的方格为例，使用图形表示解法步骤如下：

编码：

将状态转移方程转换为递归代码：

int uniquePaths_recursion(int m, int n)
{
    if(m==0 || n==0)
    {
        return 1;
    }

    return uniquePaths_recursion(m-1, n) + uniquePaths_recursion(m, n-1);
}

int uniquePaths(int m, int n)
{
    return uniquePaths_recursion(m-1, n-1);
}

不出所料 超时了。。。

分析：

超时的原因很明显，因为部分方格在递归算法中被重复计算了。

以3*3的矩阵为例，中间一格（1，1），会在（1，2）点作为左方时执行一遍递归，又会被（2，1）点作为上方时执行一遍递归。

在更大尺寸的矩阵中重复执行计算的格子就更多了，也就导致了算法执行超时。

修改：

老办法，空间换时间。
题目中有说明m,n<=100，直接创建一个100*100的二维数组，用于存储每个方格计算出的路径数。
如果该坐标在数组中的值非0，说明之前计算过路径数，直接使用即可，反之，进行递归计算。

int uniquePaths_recursion(int m, int n, int buf[100][100])
{
    if(m==0 || n==0)
    {
        buf[m][n] = 1;
        return 1;
    }

    int up = 0, left = 0;
    if(!buf[m-1][n])
    {
        up = uniquePaths_recursion(m-1, n, buf);
    }
    else
    {
        up = buf[m-1][n];
    }

    if(!buf[m][n-1])
    {
        left = uniquePaths_recursion(m, n-1, buf);
    }
    else
    {
        left = buf[m][n-1];
    }
    buf[m][n] = up+left;
    return buf[m][n];
}

int uniquePaths(int m, int n)
{
    int buf[100][100] = {0};
    int ret = uniquePaths_recursion(m-1, n-1, buf);
    return ret;
}

优化

m，n在不是100时使用二维数组有点浪费，想要进一步优化内存。

由于C语言的特性问题，如果还是想以二维的形式组织缓存表，列数是需要固定的，
也就是只能优化到m*100，因此直接将二维的表格使用一维形式存储数据（反正二维数组在内存中也是一样的连续内存），根据传入的m，n计算大小malloc内存。

int uniquePaths_recursion(int n, int m_curr, int n_curr, int *buffer)
{
    if(m_curr==0 || n_curr==0)
    {
        return 1;
    }

    int up = 0, left = 0;
    if(!(*(buffer+((m_curr-1)*n+n_curr))))
    {
        up = uniquePaths_recursion(n, m_curr-1, n_curr, buffer);
    }
    else
    {
        up = *(buffer+((m_curr-1)*n+n_curr));
    }

    if(!(*(buffer+(m_curr*n+n_curr-1))))
    {
        left = uniquePaths_recursion(n, m_curr, n_curr-1, buffer);
    }
    else
    {
        left = *(buffer+(m_curr*n+n_curr-1));
    }
    *(buffer+(m_curr*n+n_curr)) = up+left;
    return up+left;
}

int uniquePaths(int m, int n)
{
    int *buf = malloc(sizeof(int)*m*n);
    int ret = uniquePaths_recursion(n, m-1, n-1, buf);
    free(buf);
    return ret;
}