leetcode 62.不同路径

思路：动态规划

这里的状态方程我们很轻松就能看出来，就是对于路，我们是向下走还是向右走，所以就只有这两种状态。我们定义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];
    }
};