动态规划算法：05.路径问题_不同路径_C++
题目链接：LCR 098. 不同路径 - 力扣（LeetCode）
https://leetcode.cn/problems/2AoeFn/description/
一、题目解析
题目：
解析：
由题我们可知，在一个网格中，机器人需要从左上角出发，走到右下角的位置即可，每次可以选择往右或者往下走一步，直到终点，期间我们有很多种方法走到终点，最终答案即是，我们有多少种方法走到终点。
二、算法原理
1、状态表示
我们在状态标识的时候，一般都会创建一个数组dp，也就是我们所说的dp表，我们要做的就是把每一个状态的值填入这个表内，最终这个表内的某一个值可能就是我们要返回的值。
状态简单理解就是dp表内某一个值代表的含义。
如何确定状态表示
- 题目要求
简单的题目里一般会给出
- 经验+题目要求
越学越深入，动态规划也是熟能生巧，在题目中没有明显给出的时候，我们就要凭借自己做题的经验来确定，所以就需要我们大量的做题。
- 分析问题的过程中，发现重复子问题
分析问题的过程中把重复子问题抽象成我们的状态表示，这个更难理解，一切的基础都是我们先对动态规划算法熟练运用。我也不懂，我们慢慢来。
综上：我们通常会以一个位置为结尾或者开始求得我们想要的答案
那我们的这道题得状态表示是什么样的：
我们根据做题的经验，这道题还是选用最经典的，以某一个位置为结尾
状态表示：dp[i][j]表示为到达某一个位置时的所有路径方法
2、状态转移方程
确定状态表示之后我们就可以根据状态标识推出状态转移方程
状态转移方程是什么？
不讲什么复杂的，简单来说状态转移方程就是 dp[i][j]等于什么 dp[i][j]=？
这个就是状态转移方程，我们要做的，就是推出dp[i][j]等于什么
我们根据状态表示再结合题目+经验去推理转移方程，这一步也是我们整个解题过程中最难的一步
我们在这道题先简单了解下什么是状态转移方程，之后比较难的题目再细推
状态方程推理：
我们先画一个三行四列的表格,假设机器人走到了三行三列的位置s[2][2]：
那机器人是怎么到达这个地方的呢？
机器人只能向右或者向下走，那么走到s[2][2]位置就需要从s[1][2]或者s[2][1]位置走一步，根据状态表示我们知道，既然我们dp[i][j]应该表示为到达该地的所有路径方法，那么dp[i-1][j]和dp[i][j-1]也是表达到达(i-1,j)与(i,j-1)位置的所有路径数，既然这两个位置都可以到(i,j)位置，那么(i-1,j)与(i,j-1)位置的所有路径数dp[i-1][j]和dp[i][j-1]相加就是到达(i,j)位置的所有路径数了。
所以状态表示方程为 dp[i][j]=dp[i-1][j]+dp[i][j-1]
3、初始化
我们创建dp表就是为了把他填满，我们初始化是为了防止在填表的过程中越界
怎么谈越界？
解释：
当机器人在左上角位置不动时，我们也把这当作是到达位置s[0][0]的一种方法，并且只有一种，那我们机器人在往右走一步到s[0][1]时，我们去算dp[0][1]，我们是需要知道其上面位置的dp[-1][1]与左边位置的dp[0][0]，才可以计算出该位置的dp[0][1]，但是我们没有s[-1][1]这个位置，就会造成越界
同样，我们这个二维数组的左边一列与最上方一行，都是存在越界问题的，那我们应该怎么解决呢？
我们只需要在创建dp表时，让其行列都各比原数组多一，但我们需要注意，我们需要保证机器人出发点的dp值为1，才可保证后续填表正确，
我们只需要管出发点即可，原数组最左列与最上行他们只能从出发点开始走，也就是说，他们只有一种路径，就是从出发点一直向右或者向下
我们只能从图中所标两个位置走到出发点，但我们又得保证出发点的dp值为1，根据状态表示方程我们知道，需要将这两个位置中的一个初始化为1，才能保证。
另外，其它位置初始化应该都为0，在保证不越界的同时，也要保证填表正确。
4、填表顺序
从左到右、从上到下，依次填写
5、返回值
终点的dp值
三、编写代码
class Solution {
public:int uniquePaths(int m, int n) {
//1、创建dp表vector<vector<int>>dp(m+1,vector<int>(n+1));
//2、初始化dp[0][1]=1;if(m==1||n==1){return 1;}
//3、填表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];}}
//4、返回值return dp[m][n];}
};