一、问题描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3的网格。有多少不同的路径？ 注意： m 和 n 的值均不超过 100。
二、方案一：动态规划
1、思路
动态规划的核心思想是将大问题分解为小问题，然后逐步解决。
- 定义状态：
dp[i][j]表示从左上角到达位置(i, j)的不同路径数量。 - 状态转移方程：
dp[i][j] = dp[i-1][j] + dp[i][j-1]，因为机器人只能向下或向右移动。 - 初始化：第一行和第一列的
dp值为 1，因为只有一种方法到达这些位置。 - 返回值：
dp[m-1][n-1]，即右下角的路径数量。
2、代码实现
go
func uniquePaths(m int, n int) int {
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
// 初始化第一行和第一列
for i := 0; i < m; i++ {
dp[i][0] = 1
}
for j := 0; j < n; j++ {
dp[0][j] = 1
}
// 动态规划填表
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
dp[i][j] = dp[i-1][j] + dp[i][j-1]
}
}
return dp[m-1][n-1]
}3、复杂度分析
- 时间复杂度：O(m*n)，我们需要遍历整个网格。
- 空间复杂度：O(m*n)，用于存储动态规划表。
三、方案二：组合数学
1、思路
从左上角到右下角，总共需要向下移动 m-1 步，向右移动 n-1 步。因此，总共需要移动 m+n-2 步。 问题转化为：从 m+n-2 步中选择 m-1 步向下移动或 n-1 步向右移动的方式数，这是一个组合问题。
2、代码实现
go
func uniquePaths(m int, n int) int {
// 计算组合数 C(m+n-2, m-1) 或 C(m+n-2, n-1)
return combination(m+n-2, m-1)
}
// 计算组合数 C(n, k)
func combination(n, k int) int {
if k > n-k {
k = n - k
}
res := 1
for i := 0; i < k; i++ {
res *= n - i
res /= i + 1
}
return res
}3、复杂度分析
- 时间复杂度：O(m)，主要取决于计算组合数的时间。
- 空间复杂度：O(1)，不需要额外的空间。
四、总结
| 方案 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 动态规划 | O(m*n) | O(m*n) | 适用于一般情况，易于理解和实现 |
| 组合数学 | O(m) | O(1) | 在 m 和 n 较大时更高效，需要组合数学知识 |
根据题目要求，两种方案均能满足需求。如果 m 和 n 较大，建议使用组合数学方法，以减少时间和空间复杂度。