62.不同路径

题目描述

一个机器人位于一个 m x n 网格的左上角，只能向右或向下移动一步，问从起点到达右下角共有多少条不同的路径。

示例 1:

输入: m = 3, n = 7
输出: 28

示例 2:

输入: m = 3, n = 2
输出: 3

解题思路一：动态规划

设 f[i][j] 为到达坐标 (i, j) 的路径数。只能从上方 (i-1, j) 或左方 (i, j-1) 来到 (i, j)，故转移为：

f[i][j] = f[i-1][j] + f[i][j-1]，边界为第一行与第一列均为 1。

代码实现

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int m = scanner.nextInt();
        int n = scanner.nextInt();

        Solution solution = new Solution();
        int result = solution.uniquePaths(m, n);
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++) { f[i][0] = 1; }
        for (int j = 0; j < n; j++) { f[0][j] = 1; }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
}

解题思路二：组合数学

共需向右 n-1 次、向下 m-1 次，步数总计 m+n-2。本质为从这 m+n-2 次中选择 m-1 个位置向下：

答案为组合数 C(m+n-2, m-1)。

代码实现（迭代计算）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int m = scanner.nextInt();
        int n = scanner.nextInt();

        Solution solution = new Solution();
        int result = solution.uniquePaths(m, n);
        System.out.println(result);

        scanner.close();
    }
}

class Solution {
    public int uniquePaths(int m, int n) {
        int a = m + n - 2, b = Math.min(m - 1, n - 1);
        long res = 1;
        for (int i = 1; i <= b; i++) { res = res * (a - b + i) / i; }
        return (int) res;
    }
}

复杂度分析

• 时间复杂度：O(mn)（动态规划），或 O(min(m,n))（组合数学）。
• 空间复杂度：O(mn)（二维数组），可优化为 O(n) 使用一维滚动数组。

网格只能右或下移动，路径数由局部两方向累加，或整体用组合数一次求出。