[线性dp]leetcode62：不同的路径(medium)

线性dp]leetcode62：不同的路径(medium)"/>

[线性dp]leetcode62：不同的路径(medium)

题目：

题解：

2022/5/9：线性 dp 的一般思路，使用 y 式 dp 分析法很快能得到本题的状态转移方程。

---

思路：动态规划

• dp[i][j]表示表示到达点[i,j]的路径数
• 状态转移方程：
• ①：i==0||j==0时，则·f[i][j]=1，表示边界上的路径只有一条
• ②：i!=0&&j!=0时，则f[i][j]=f[i-1][j]+f[i][j-1]，表示到达点[i,j]与该点正上和正右的点有关

代码如下：

const int N = 110;
int f[N][N];// f[i][j]表示走到(i,j)这个点的路径个数
class Solution {
public:// 线性dpint uniquePaths(int n, int m) {memset(f,0,sizeof f);// 初始化边界情况：位于第一行和第一列的路径数为1for(int i=0;i<n;++i)f[i][0]=1;for(int j=0;j<m;++j)f[0][j]=1;// 自上而下进行状态转移，由于f[i][j]由f[i-1][j]与f[i][j-1]推出来，所用到i-1，j-1都要是经过计算过的状态// 所以 i j 都要从小到大的进行枚举for(int i=1;i<n;++i)for(int j=1;j<m;++j)f[i][j]=f[i-1][j]+f[i][j-1];// 返回终点的路径个数return f[n-1][m-1];}
};