线性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];}
};
更多推荐
[线性dp]leetcode62:不同的路径(medium)
发布评论