LeetCode 上的 DP：3 个带有递推公式的题目

动态规划：三题LeetCode问题的直观解法

动态规划（DP）通过递推关系解决计数和优化问题。让我们分析问题62（不同路径）、64（最小路径和）和70（爬楼梯）。每个问题都展示了DP的关键特性：最优子结构和重叠子问题。

不同路径：网格路径计数

一个机器人在m × n网格上从(0,0)移动到(m-1,n-1)，只能向右或向下移动。求不同路径的数量。

任何路径由(m-1)次向下移动和(n-1)次向右移动组成。组合解法使用二项式系数C(m+n-2, m-1)。然而，面试中通常期望算法解法。

定义dp[i][j]为到达单元格(i,j)的路径数。递推关系：

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

边界条件：

• dp[0][j] = 1（第一行）
• dp[i][0] = 1（第一列）

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

时间复杂度O(m·n)。该解法使用不相交路径集的加法规则。

最小路径和：最小化路径成本

给定一个包含非负数的m × n网格。当只能向右或向下移动时，求从(0,0)到(m-1,n-1)路径上数值的最小和。

贪心算法（选择局部最小值）会失败——它会导致陷入高数值的死胡同。需要全局优化。

定义dp[i][j]为到达(i,j)的最小成本。递推关系：

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

边界条件：

dp[0][0] = grid[0][0]
for j in range(1, n): dp[0][j] = grid[0][j] + dp[0][j-1]
for i in range(1, m): dp[i][0] = grid[i][0] + dp[i-1][0]

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for j in range(1, n):
            dp[0][j] = grid[0][j] + dp[0][j - 1]
        for i in range(1, m):
            dp[i][0] = grid[i][0] + dp[i - 1][0]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])
        return dp[-1][-1]

复杂度O(m·n)。每个值都用于所有后续单元格。

爬楼梯：DP中的斐波那契数

爬n级楼梯（1 ≤ n ≤ 45），每次可以爬1级或2级。求爬楼梯的方法数。

对于n=1：1种方法

n=2：2种方法（1+1, 2）

n=3：3种方法（1+1+1, 1+2, 2+1）

递推关系：

dp[n] = dp[n-1] + dp[n-2]

简单递归会导致指数复杂度O(φ^n)，因为重复计算。DP数组解决该问题：

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1], dp[2] = 1, 2
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

优化版本使用两个变量实现O(1)内存。

动态规划问题的特征

当满足两个条件时应用DP：

• 最优子结构：最优解由子问题的最优解组成。
• 重叠子问题：相同的子问题被多次计算。

| 问题 | 最优子结构 | 重叠子问题 |

|--------|-------------------------|---------------------------|

| 不同路径 | 相邻单元格路径之和 | 到达每个单元格的路径重叠 |

| 最小路径和 | 邻居的最小成本 | 成本用于所有下方/右侧单元格 |

| 爬楼梯 | n-1和n-2之和 | 递归调用重复 |

关键要点

• 递推关系定义了DP的本质：dp[i][j]仅依赖于相邻已计算值。
• 边界条件单独填充第一行/列或基本情况。
• 时间复杂度在正确的表格实现中始终为O(输入大小)。
• 内存可以优化：对于网格——一行，对于线性问题——两个变量。
• 组合数学通常提供数学捷径，但算法解法在面试中更重要。

— Editorial Team