力扣第 62 题 不同路径

题目描述

一个机器人位于一个 $m\times n$ 网格的左上角（起始点在下图中标记为 “Start” ）。
机器人每次只能向下或向右移动一步。机器人试图到达网格的右下角（标记为 “Finish”）。

问总共有多少条不同的路径？

---

示例 1:

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

示例 2:

输入: m = 3, n = 2
输出: 3
解释:
从左上角到右下角总共有 3 条路径：
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

提示:

• $1\le m,n\le 100$
• 答案保证小于等于 $2\times 10^9$。

---

解题思路

这个问题可以用 动态规划 或 组合数学 来解决。

动态规划解法

1. 定义状态：

   • 令 dp[i][j] 表示从起点到达网格 $(i,j)$ 的不同路径数。

2. 状态转移方程：

   • 到达网格 $(i,j)$ 的路径数等于从上方到达 $(i-1,j)$ 和从左方到达 $(i,j-1)$ 的路径数之和：

     $dp[i][j]=dp[i-1][j]+dp[i][j-1]$

3. 初始化：

   • 第一行和第一列的路径数均为 1，因为机器人只能直线到达这些位置：

     $dp[0][j]=1,dp[i][0]=1$

4. 结果：

   • 最终答案为 dp[m-1][n-1]。

5. 时间和空间复杂度：

   • 时间复杂度：$O(m\times n)$
   • 空间复杂度：
     • 如果直接使用二维数组：$O(m\times n)$
     • 可以通过优化为一维数组，空间复杂度降为 $O(n)$。

---

C 代码实现

方法 1：二维数组动态规划

#include <stdio.h>
#include <stdlib.h>

int uniquePaths(int m, int n) {
    // 动态规划数组
    int dp[m][n];

    // 初始化第一行和第一列
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    for (int j = 0; j < n; j++) {
        dp[0][j] = 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];
}

int main() {
    int m = 3, n = 7;
    printf("不同路径的数量: %d\n", uniquePaths(m, n));
    return 0;
}

---

方法 2：一维数组动态规划

通过优化动态规划为一维数组，降低空间复杂度：

#include <stdio.h>
#include <stdlib.h>

int uniquePaths(int m, int n) {
    // 使用一维数组保存当前行的路径数
    int *dp = (int *)malloc(n * sizeof(int));

    // 初始化数组，第一行的所有值都为 1
    for (int j = 0; j < n; j++) {
        dp[j] = 1;
    }

    // 动态规划计算路径数
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
        }
    }

    // 获取结果
    int result = dp[n - 1];
    free(dp); // 释放内存
    return result;
}

int main() {
    int m = 3, n = 7;
    printf("不同路径的数量: %d\n", uniquePaths(m, n));
    return 0;
}

---

方法 3：组合数学解法

机器人从左上角到右下角共需要移动 $m-1$ 次向下和 $n-1$ 次向右，总共 $m+n-2$ 步。在这些步中，选择 $m-1$ 步向下的组合数为答案：

$C(m+n-2,m-1)=\frac{(m+n-2)!}{(m-1)!(n-1)!}$

#include <stdio.h>

long long combination(int a, int b) {
    long long res = 1;
    for (int i = 1; i <= b; i++) {
        res = res * (a - i + 1) / i;
    }
    return res;
}

int uniquePaths(int m, int n) {
    return combination(m + n - 2, m - 1);
}

int main() {
    int m = 3, n = 7;
    printf("不同路径的数量: %d\n", uniquePaths(m, n));
    return 0;
}

---

复杂度分析

方法	时间复杂度	空间复杂度
二维动态规划	$O(m\times n)$	$O(m\times n)$
一维动态规划	$O(m\times n)$	$O(n)$
组合数学	$O(\min (m,n))$	$O(1)$

---

总结

• 如果 $m$ 和 $n$ 都较小，使用二维动态规划最直观。
• 如果需要节省空间，可以使用一维动态规划。
• 如果只关心结果且能处理大数，组合数学解法效率最高。

原文地址：https://blog.csdn.net/weixin_48941116/article/details/144008625

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！