【LeetCode】动态规划—不同路径（附完整Python/C++代码）

Albert_Lsk

1820人浏览 · 2024-09-25 16:30:10

Albert_Lsk · 2024-09-25 16:30:10 发布

前言

一个机器人位于一个 $m * n$ 网格的左上角（起始点）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（终点）。问总共有多少条不同的路径？

题目描述

在这里插入图片描述

基本思路

1. 问题定义:

2. 理解问题和递推关系:

问题的本质是计算从起点到终点的所有可能路径数。
关键观察：到达任一点的路径数等于到达其上方点的路径数加上到达其左方点的路径数。
递推关系: 设 $d p [i] [j]$ 表示到达位置 $(\mathrm{i}, \mathrm{j})$ 的不同路径数, 则: $d p [i] [i] = d p [i - 1] [j] + d p [i] [j - 1]$
边界条件: 第一行和第一列的所有位置的路径数都是 $1$ , 因为只有一种方式到达这些位置。

3. 解决方法:

3.1动态规划方法

创建一个 $m * n$ 的二维数组 $d p$ 。
初始化第一行和第一列的值为 $1$ 。
从左上到右下填充 $d p$ 数组, 使用递推公式: $d p [i] [j] = d p [i - 1] [j] + d p [i] [j - 1]$ 。
最终结果为 $d p [m - 1] [n - 1]$ 。

3.2 空间优化的动态规划

使用一维数组 $d p$ 代替二维数组。
初始化 dp 数组的所有元素为 $1$ 。
逐行更新 $d p$ 数组, 每次更新时, 当前值等于其自身（上一行的值）加上前一个元素（左边的值)。
最终结果为 $d p [n - 1]$ 。

4. 进一步优化:

数学方法 (组合数学)

观察: 从起点到终点总共需要移动 $m + n - 2$ 步, 其中 $m - 1$ 步向下, $n - 1$ 步向右。
问题转化为：在 $m + n - 2$ 步中选择 $m - 1$ 步向下（或选择 $n - 1$ 步向右）的方案数。
这等价于计算组合数 $C_{m+n-2}^{m-1}$ 或 $C_{m+n-2}^{n-1}$ 。
使用组合数公式可以直接计算结果, 无需使用动态规划。

5. 小总结:

动态规划方法提供了一种直观且易于理解的解法，适用于理解问题的本质和解决类似的路径问题。
空间优化的动态规划方法在保持时间复杂度的同时，显著降低了空间复杂度，适用于处理较大规模的输入。
数学方法利用组合数学知识，提供了最优的时间和空间复杂度，但需要注意大数运算可能带来的溢出问题。
这个问题是动态规划的经典案例，掌握它对于解决更复杂的动态规划问题很有帮助。同时，它也展示了如何通过数学思维来优化算法，这在算法设计中是一个非常有价值的技能。
在实际应用中，可以根据具体的需求、输入规模和计算环境来选择最适合的方法。

以上就是不同路径问题的基本思路。

代码实现

Python3代码实现

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 初始化一个一维DP数组,初始值都为1
        dp = [1] * n
        
        # 从第二行开始逐行更新DP数组
        for i in range(1, m):
            for j in range(1, n):
                # 当前位置的路径数等于其上方和左方的路径数之和
                dp[j] += dp[j-1]
        
        # 返回右下角位置的路径数
        return dp[-1]

    def uniquePathsMath(self, m: int, n: int) -> int:
        # 总步数
        N = m + n - 2
        # 向下的步数
        k = min(m - 1, n - 1)
        
        # 计算组合数 C(N, k)
        res = 1
        for i in range(1, k + 1):
            res = res * (N - k + i) // i
        
        return res

Python 代码解释

这段代码定义了一个名为 Solution 的类，其中包含两个方法 uniquePaths 和 uniquePathsMath，用于计算从网格的左上角到右下角的不同路径数量。

1. uniquePaths 方法:

初始化一个—维动态规划（DP）数组 $d p$ ，长度为 $n$ ，所有元素初始值为 $1$ 。这表示在第—行的每个位置都有 $1$ 条路径。
从第二行开始，逐行更新 DP 数组。对于每个位置 $（ i ， j ）$ ，其路径数等于上方位置 $（ i - 1, j ）$ 和左方位置 $（ i ， j - 1 ）$ 的路径数之和。
最后返回右下角位置的路径数，即 $\mathrm{dp}[-1]$ 。

2. uniquePathsMath 方法:

计算总步数 $N$ ，等于 $m + n - 2$ ，表示从起点到终点需要的总步数。
计算向下的步数 $k$ ，取 $m - 1$ 和 $n - 1$ 中的较小值。
通过组合数公式计算从 $N$ 步中选择 $k$ 步向下的方式数，返回结果 $res$ .

这两个方法分别使用动态规划和数学组合的方式来解决相同的问题。

C++代码实现

class Solution {
public:
    int uniquePaths(int m, int n) {
        // 初始化一个一维DP数组,初始值都为1
        vector<int> dp(n, 1);
        
        // 从第二行开始逐行更新DP数组
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 当前位置的路径数等于其上方和左方的路径数之和
                dp[j] += dp[j-1];
            }
        }
        
        // 返回右下角位置的路径数
        return dp.back();
    }
    
    int uniquePathsMath(int m, int n) {
        // 总步数
        long long N = m + n - 2;
        // 向下的步数
        int k = min(m - 1, n - 1);
        
        // 计算组合数 C(N, k)
        long long res = 1;
        for (int i = 1; i <= k; i++) {
            res = res * (N - k + i) / i;
        }
        
        return (int)res;
    }
};