思路:动态规划
这里的状态方程我们很轻松就能看出来,就是对于路,我们是向下走还是向右走,所以就只有这两种状态。我们定义dp[i][j]为在到达坐标(i,j)处所有的路线个数。
这样的话,我们就写出状态方程:
dp[i][j]=dp[i-1][j]+dp[i][j-1]。
注意:这里需要特别关注一下边界条件,我们刚开始是在左上角的,所以在第一行的所有列就只有向右这一种选择,也就是只有一种路线;同理,我们在第一列的时候就只有向下这一种选择,也就是只有一种路径。
上代码:
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>>dp(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++)
dp[i][1]=1;
for(int j=1;j<=n;j++)
dp[1][j]=1;
for(int i=2;i<=m;i++){
for(int j=2;j<=n;j++){
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m][n];
}
};