LeetCode LCR 098. 不同路径

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
2. 解法二：组合数学
相似题目

题目描述

✅ LCR 098. 不同路径

思路分析

解法一：动态规划（推荐）

核心思路：

机器人只能向右或向下移动，因此到达格子 (i, j) 的路径只来自上方 (i-1, j) 或左方 (i, j-1)。

状态定义：dp[i][j] 表示从左上角 (0, 0) 到达 (i, j) 的不同路径数。

边界条件：第一行和第一列的所有格子只有唯一路径，均初始化为 1。

转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]

空间优化（滚动数组）：每行计算只依赖上一行，可用一维数组原地更新：dp[j] += dp[j-1]，其中 dp[j] 保存上一行的值（来自上方），dp[j-1] 是当前行左方的值。

复杂度分析：

时间复杂度：O(m × n)，其中 m、n 分别为网格的行数和列数

空间复杂度：O(n)，使用一维滚动数组，n 为列数

class Solution {

  public int uniquePaths(int m, int n) {
    // dp[j] 表示到达当前行第 j 列的不同路径数
    int[] dp = new int[n];
    // 初始化第一行：每个格子只有一种路径（一直向右）
    Arrays.fill(dp, 1);
    for (int i = 1; i < m; i++) {
      for (int j = 1; j < n; j++) {
        // dp[j] 原值为上一行同列（来自上方），加上 dp[j-1] 即来自左方
        dp[j] += dp[j - 1];
      }
    }
    return dp[n - 1];
  }
}

func uniquePaths(m int, n int) int {
	// dp[j] 表示到达当前行第 j 列的不同路径数
	dp := make([]int, n)
	// 初始化第一行：每个格子只有一种路径（一直向右）
	for j := 0; j < n; j++ {
		dp[j] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			// dp[j] 原值为上一行同列（来自上方），加上 dp[j-1] 即来自左方
			dp[j] += dp[j-1]
		}
	}
	return dp[n-1]
}

解法二：组合数学

核心思路：

从左上角到右下角，机器人共需走 m + n - 2 步，其中恰好 m - 1 步向下，n - 1 步向右。

问题转化为：从 m + n - 2 步中选取 m - 1 步向下，方案数即组合数 $C_{m+n-2}^{m-1}$。

计算公式：$C_{m+n-2}^{m-1} = \dfrac{(m+n-2)!}{(m-1)! \cdot (n-1)!}$

实现时逐步累乘再除，避免大数溢出：遍历 i 从 1 到 min(m-1, n-1)，依次计算 result = result * (m + n - 2 - (i-1)) / i。

复杂度分析：

时间复杂度：O(min(m, n))，只需遍历较小维度次数

空间复杂度：O(1)，只使用常数级别的额外空间

class Solution {

  public int uniquePaths(int m, int n) {
    // 计算组合数 C(m+n-2, min(m-1, n-1))，取较小值减少计算量
    long result = 1;
    int k = Math.min(m - 1, n - 1);
    for (int i = 1; i <= k; i++) {
      // 逐步累乘：result = result * (m+n-2-(i-1)) / i
      result = result * (m + n - 1 - i) / i;
    }
    return (int) result;
  }
}

func uniquePaths(m int, n int) int {
	// 计算组合数 C(m+n-2, min(m-1, n-1))，取较小值减少计算量
	result := 1
	k := m - 1
	if n-1 < k {
		k = n - 1
	}
	for i := 1; i <= k; i++ {
		// 逐步累乘：result = result * (m+n-1-i) / i
		result = result * (m + n - 1 - i) / i
	}
	return result
}

相似题目

题目	难度	考察点
63. 不同路径 II	中等	动态规划、障碍物处理
64. 最小路径和	中等	动态规划、网格路径
120. 三角形最小路径和	中等	动态规划、路径求和
221. 最大正方形	中等	二维动态规划
980. 不同路径 III	困难	回溯、状态压缩
174. 地下城游戏	困难	动态规划、逆向推导
931. 下降路径最小和	中等	动态规划、网格路径

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/23466977