【动态规划专栏】专题二：路径问题--------1.不同路径

题目来源

本题来源为：

Leetcode62. 不同路径

题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

题目解析

我们可以模拟一下机器人的过程：

算法原理

1.状态表示

经验+题目要求

对于本题而言就是：

dp[i][j]表示：走到[i,j]位置的时候，一共有多少种方式。

2.状态转移方程

机器人到达[i,j]位置有两种，一种从上面过来，一种从左边过来。

根据最近的一步划分问题：

因此状态方程为：

dp[i][j]=dp[i-1][j]+dp[i][j-1]

3.初始化

初始化之前先看一下会有什么位置会发生越界访问：

因为机器人要么从上边下来，要门从左边下来，因此会发生越界的为第一排和第一列。

我们基本上会采取以下的初始化方式，在原二维数组的基础上加一行一列。

加上之后要注意两点：

下标映射注意新表与原始的下标关系即可，而虚拟节点里面的值要根据情况而定：

观察一下，第二行从第三个开始需要它上面的和左面的两个一起决定，而且要保证它上面的也就是虚拟节点不能被选上（也就是不影响结果）那么它应该就是负无穷，但是本题的范围：

所以我们赋值为0就不会被选上了。依次内推：

因为第二排的第二个位置会决定其他位置的值，因此要赋值为1；这里有两种，可以从上面虚拟节点也可以从左面的虚拟节点进行赋值。

4.填表顺序

整体从上往下，每排从左往右。

5.返回值

根据题目要求，需要返回右下角的值，因此返回：

dp[m][n]

代码实现

动态规划的代码基本就是固定的四步：

1.创建dp表
2.初始化
3.填表
4.返回值

本题完整代码实现：

class Solution 
{
public:
    int uniquePaths(int m, int n) 
    {
            // 1.创建dp表
            // 2.初始化
            // 3.填表
            // 4.返回值
            vector<vector<int>> dp(m+1,vector<int>(n+1));
            dp[0][1]=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][n];
    }
};

时间复杂度：O(MN)
空间复杂度：O(MN)