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

这篇具有很好参考价值的文章主要介绍了【动态规划专栏】专题二：路径问题--------1.不同路径。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。通过本专栏的深入学习，你可以了解并掌握算法。

💓博主csdn个人主页：小小unicorn
⏩专栏分类：动态规划专栏
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

题目来源

本题来源为：

Leetcode62. 不同路径

题目描述

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

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

问总共有多少条不同的路径？
【动态规划专栏】专题二：路径问题--------1.不同路径,算法专栏,# 动态规划算法专栏,动态规划,算法,c++

题目解析

我们可以模拟一下机器人的过程：
【动态规划专栏】专题二：路径问题--------1.不同路径,算法专栏,# 动态规划算法专栏,动态规划,算法,c++

算法原理

1.状态表示

经验+题目要求
【动态规划专栏】专题二：路径问题--------1.不同路径,算法专栏,# 动态规划算法专栏,动态规划,算法,c++

对于本题而言就是：
dp[i][j]表示：走到[i,j]位置的时候，一共有多少种方式。

2.状态转移方程

机器人到达[i,j]位置有两种，一种从上面过来，一种从左边过来。
【动态规划专栏】专题二：路径问题--------1.不同路径,算法专栏,# 动态规划算法专栏,动态规划,算法,c++
根据最近的一步划分问题：

因此状态方程为：
【动态规划专栏】专题二：路径问题--------1.不同路径,算法专栏,# 动态规划算法专栏,动态规划,算法,c++

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

3.初始化

初始化之前先看一下会有什么位置会发生越界访问：
【动态规划专栏】专题二：路径问题--------1.不同路径,算法专栏,# 动态规划算法专栏,动态规划,算法,c++
因为机器人要么从上边下来，要门从左边下来，因此会发生越界的为第一排和第一列。

我们基本上会采取以下的初始化方式，在原二维数组的基础上加一行一列。
【动态规划专栏】专题二：路径问题--------1.不同路径,算法专栏,# 动态规划算法专栏,动态规划,算法,c++
加上之后要注意两点：

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

观察一下，第二行从第三个开始需要它上面的和左面的两个一起决定，而且要保证它上面的也就是虚拟节点不能被选上（也就是不影响结果）那么它应该就是负无穷，但是本题的范围：
【动态规划专栏】专题二：路径问题--------1.不同路径,算法专栏,# 动态规划算法专栏,动态规划,算法,c++
所以我们赋值为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];
    }
};