题目描述

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

示例：
输入：m = 3, n = 7
输出：28

题目分析

动态规划

设 dp[i][j] 表示移动至 i, j 的路径条数，dp[i][j] = dp[i-1][j] + dp[i][j-1]
可进一步将空间优化为一层 dp[j] = dp[j] + dp[j - 1]

时间复杂度 O(m * n)

数学

一共需要移动 m + n – 2 次，横向 n – 1 次，纵向 m – 1 次
问题转化为从 m + n – 2 次中选择 n – 1 次，即 C(m + n – 2, n – 1)
C(m, n) = A(m, n) / A(n, n)，数据量大会溢出，不能分开计算，需要结合在一起计算。

时间复杂度 O(min(m, n))

Java

public int uniquePaths(int m, int n) {
    if (m < n) {
        int temp = m;
        m = n;
        n = temp;
    }
    int sum = m + n - 2;
    int col = n - 1;
    long ans = 1;
    for (int i = sum, j = 1; i > sum - col; i--, j++) {
        ans *= i;
        ans /= j;
    }
    return (int) ans;
}

public int uniquePaths2(int m, int n) {
    int[] dp = new int[n];
    dp[0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}

Kotlin

fun uniquePaths(m: Int, n: Int): Int {
    val a = if (m < n) n else m
    val b = if (m < n) m else n
    val sum = a + b - 2
    val col = b - 1
    var ans = 1L
    var j = 1
    for (i in sum downTo sum - col + 1) {
        ans *= i
        ans /= j++
    }
    return ans.toInt()
}

fun uniquePaths2(m: Int, n: Int): Int {
    val dp = Array(m) { IntArray(n) }
    dp[0][0] = 1
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (i == 0 && j == 0) {
                continue
            }
            val up = if (i >= 1) dp[i - 1][j] else 0
            val left = if (j >= 1) dp[i][j - 1] else 0
            dp[i][j] = up + left
        }
    }
    return dp[m - 1][n - 1]
}