leetcode - 62. 不同路径

62. 不同路径

————————————————————————————————————————————一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？
说明：m 和 n 的值均不超过 100。

示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右

示例 2:
输入: m = 7, n = 3
输出: 28

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
————————————————————————————————————————————
解题思路：
创建一个m x n的矩阵，每个矩阵中数字的值表示从[0,0]到该点的不同路径的数量。易知，第一行中所有点的不同路径的数量都是1，从第二行开始，从[0,0]到每个点的不同的路径的数量是其左边和上边的路径的总和。注意每一行的最开始的点的位置的特殊性。其C++代码如下：

class Solution {
public:
    int uniquePaths(int m, int n) 
    {
        vector<vector<int>> dp(m,vector<int>(n));  #创建一个矩阵
        for(int i=0;i<n;i++)  #将第一行的所有的数据都标记为1
        {
            dp[0][i]=1;
        }
        for(int i=1;i<m;i++)  #从第二行开始进行动态规划
        {
            for(int j=0;j<n;j++)
            {
                if(j==0)
                    dp[i][j] = dp[i][j]+dp[i-1][j];
                else
                    dp[i][j] = dp[i][j] + dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
};