从暴力递归到动态规划leetcode第62题:不同路径

1、什么是动态规划?

动态规划（英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。

2、动态规划的核心思想

动态规划的基本思想是将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解。对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。

3、leetcode案例分析

**暴力递归思路:**递归的话我们得确定递归返回的条件，因为题目限制了机器人只能往前面走，或者往右边走，所以我们第一个递归返回的条件就是机器人我位置已经大于了m或者大于了n，这时说明机器人并没有走到右下角，第二个递归条件就是当机器人走到了右下的时候，说明已经找到了一条路径。
代码实现:

class Solution {
    
public:
    int uniquePaths(int m, int n) {
    
        int i=0,j=0;
        return _uniquePaths(i,j,m-1,n-1);
    }
    int _uniquePaths(int i,int j,int m,int n)
    {
    
        if(i>m||j>n)
          return 0;

        if(i==m&&j==n)
           return 1;

        return _uniquePaths(i+1,j,m,n)+_uniquePaths(i,j+1,m,n);
    }
};

这里我另外写了一个子函数去递归，这里的i和j代表的就是机器人当前的位置，当机器人已经越界了，我们直接返回0就可以了，因为越界的情况下，再怎么走都不可能走到右下角，如果说im&&jn的话就说明我们找到了一条路径，返回1即可，最后重复递归此函数，_uniquePaths(i+1,j,m,n)就是算出机器人这时往右走的所有次数然后加上_uniquePaths(i,j+1,m,n)机器人这时往前走的所以次数，返回它们相加的次数就是能达到右下角的次数。
我们的思路是对的，但该题其实是通过不了的，因为调用的栈帧太大，超出了时间限制。
如下:

动态规划解题思路:
我们发现机器人如果想要走到右下角，就必须要走到(m-1,n)或者(m,n-1）这两个位置，而想走到(m-1，n)这个位置又必须走到(m-2,n)或者(m-1,n-1)，子问题再拆分成子问题，这就是动态规划的核心思想，我们可以创建一个二维数组dp，大小就是m*n这么大，每个位置存放的就是机器人到该位置的最大不同路径的次数这里给大家画图理解一下：

首先机器人在(0,0)这个位置，而机器人这时往前走的一列格子，都只有一种走法，机器人这时往右走的第一行也都只有一种走法，所以我全填上了1，给大家解释一下为什么，因为是不能往后走的和往左走的，所以当机器人一旦往前走，就没办法再走到第一行的格子了，反之当机器人一旦往右走，就没办法走到第一列格子了。
接下来我们要来计算其他格子的不同路径的最大次数了，而我们可以发现，其实(1,1）这个坐标它的次数其实就是能走到(1，0)的次数加上能走到(0，1）的次数，这样一行一行的计算，坐标(2，6)的值其实就是能走到右下角的不同路径的最大次数。
代码实现:

class Solution {
    
public:
    int uniquePaths(int m, int n) {
    
        int dp[m][n];
        for(int i=0;i<n;i++)
        {
    
            dp[0][i]=1;
        }
        for(int i=0;i<m;i++)
        {
    
            dp[i][0]=1;
        }
        for(int i=1;i<m;i++)
        {
    
            for(int j=1;j<n;j++)
            {
    
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};

运行结果如下:

这就是本篇博客的全部内容了，希望对大家有所帮助，感谢大家观看，喜欢的记得点赞收藏加关注哦!我会持续更新该类型的题目!