题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例
示例 1：
输入：m = 3, n = 7 输出：28示例 2：
输入：m = 3, n = 2 输出：3 解释： 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 3. 向下 -> 向右 -> 向下示例 3：
输入：m = 7, n = 3 输出：28示例 4：
输入：m = 3, n = 3 输出：6
分析
动态规划
算法思路
设 dp[i][j] 表示机器人到达第 i 行第 j 列网格的不同路径数量。
边界条件：
- 当机器人位于第一行时，由于它只能从左边的网格向右移动到达，所以对于第一行的任意列
j，都有dp[0][j] = 1。 - 当机器人位于第一列时，由于它只能从上方的网格向下移动到达，所以对于第一列的任意行
i，都有dp[i][0] = 1。
状态转移方程：
- 对于其他位置
(i, j)（i > 0且j > 0），机器人可以从上方的网格(i - 1, j)向下移动一步到达，也可以从左边的网格(i, j - 1)向右移动一步到达。因此，到达(i, j)的不同路径数量等于到达(i - 1, j)的路径数量加上到达(i, j - 1)的路径数量，即dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。
最终结果：
- 要求的是机器人到达右下角网格
(m - 1, n - 1)的不同路径数量，即dp[m - 1][n - 1]。
时间复杂度：O()
空间复杂度：O()
class Solution {
public:int uniquePaths(int m, int n) {// 创建一个二维数组 dp 来存储到达每个网格的不同路径数量std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));// 初始化第一行，因为从起点到第一行的任意位置都只有一种路径（一直向右走）for (int j = 0; j < n; ++j) {dp[0][j] = 1;}// 初始化第一列，因为从起点到第一列的任意位置都只有一种路径（一直向下走）for (int i = 0; i < m; ++i) {dp[i][0] = 1;}// 填充 dp 数组，根据状态转移方程计算到达每个位置的不同路径数量for (int i = 1; i < m; ++i) {for (int j = 1; j < n; ++j) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}// 返回到达右下角网格的不同路径数量return dp[m - 1][n - 1];}
}; 
