企业官网建设流程全解析

题目描述：

一个机器人位于一个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 = 7

dp: 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：二维 DP

class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> dp(m, vector<int>(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) { vector<int> 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]是当前行已更新的值。

复杂度分析：

方法二：组合数学

核心思路：

从(0,0)到(m-1,n-1)，总共要走m+n-2步：

• 向下m-1步

• 向右n-1步

问题转化为：从m+n-2步中选m-1步向下（或n-1步向右）。

结果 = C(m+n-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; } };

复杂度分析：

两种方法对比：

动态规划更通用（能处理障碍物等变种），组合数学更快但只适合无阻碍的情况。

总结：