动态规划5：62. 不同路径

动态规划解题步骤：

1.确定状态表示：dp[i]是什么

2.确定状态转移方程：dp[i]等于什么

3.初始化：确保状态转移方程不越界

4.确定填表顺序：根据状态转移方程即可确定填表顺序

5.确定返回值

题目链接：62. 不同路径 - 力扣（LeetCode）

题解：

1. 状态表示：dp[i]表示到达[i,j]位置有几种方法

2.状态转移方程：dp[i][j]=dp[i-1][j]+dp[i][j-1]

3.初始化：初始化第一行和第一列，值为1

4.填表顺序：遍历二维数组依次填写

5.返回值：dp[m-1][n-1]

class Solution {
public:int uniquePaths(int m, int n) {//创建dp表vector<vector<int>> dp(m);for(int i=0;i<m;++i) dp[i].resize(n);//初始化for(int i=0;i<m;++i) dp[i][0]=1;for(int j=0;j<n;++j) dp[0][j]=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];}
};//dp[i][j]=dp[i-1][j]+dp[i][j-1]

优化题解：

将初始化与填表合并，但是为了防止填表越界，需要多开一行一列空间，并且多开的空间需要填入合适的值以保证填表正确。本题需要使dp[0][1]=1，其余位置为0。注意返回值改变！

class Solution {
public:int uniquePaths(int m, int n) {//创建dp表(多开一行一列)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];}
};