题目描述一个机器人位于一个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] 从起点(0,0)到(i,j)的不同路径数。状态转移因为只能从上方或左方到达(i,j)dp[i][j] dp[i-1][j] dp[i][j-1]初始化第一行只能从左边来dp[0][j] 1第一列只能从上边来dp[i][0] 1具体过程示例m 3, n 7dp: 1 1 1 1 1 1 1 1 2 3 4 5 6 7 1 3 6 10 15 21 28 dp[2][6] 28 ✅代码实现写法1二维 DPclass Solution { public: int uniquePaths(int m, int n) { vectorvectorint dp(m, vectorint(n, 1)); 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]; } };写法2一维 DP空间优化class Solution { public: int uniquePaths(int m, int n) { vectorint dp(n, 1); // 第一行全是1 for (int i 1; i m; i) { for (int j 1; j n; j) { dp[j] dp[j-1]; // dp[j] dp[j] dp[j-1] } } return dp[n-1]; } };关键dp[j]更新前是上一行的值dp[j-1]是当前行已更新的值。复杂度分析方法时间复杂度空间复杂度二维 DPO(m × n)O(m × n)一维 DPO(m × n)O(n)方法二组合数学核心思路从(0,0)到(m-1,n-1)总共要走mn-2步向下m-1步向右n-1步问题转化为从mn-2步中选m-1步向下或n-1步向右。结果 C(mn-2, m-1)代码实现class Solution { public: int uniquePaths(int m, int n) { long long result 1; int N m n - 2; int k min(m - 1, n - 1); for (int i 1; i k; i) { result result * (N - k i) / i; } return (int)result; } };复杂度分析维度复杂度说明时间复杂度O(min(m, n))计算组合数空间复杂度O(1)只用常数个变量两种方法对比方法时间复杂度空间复杂度推荐度动态规划O(m × n)O(n)⭐⭐⭐⭐⭐组合数学O(min(m, n))O(1)⭐⭐⭐⭐动态规划更通用能处理障碍物等变种组合数学更快但只适合无阻碍的情况。总结要点说明核心思想dp[i][j] dp[i-1][j] dp[i][j-1]初始化第一行和第一列全为 1时间复杂度O(m × n)空间复杂度O(n)一维 DP