动态规划入门

什么是动态规划？

动态规划（Dynamic Programming，简称 DP）是一种算法设计技术，它的核心思想是：

将复杂问题分解为更小的子问题，存储子问题的解，避免重复计算。

一秒钟听懂的比喻

有人问你：1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = ?

你费力地数了一下，回答：“8”。

接着，那个人在后面又加了一个 + 1，问你：“现在等于几？”

你会毫不犹豫地回答：“9”。

为什么这次你算得这么快？

因为你记住了前面的结果是 8，你只需要算 8 + 1 = 9，而不需要从头再数一遍。

这就是动态规划的核心：记住过去，指导未来。

交互式可视化演示

下面是一个网格路径问题的动态规划可视化演示，帮助你直观理解 DP 的工作原理：

动态规划三要素

1. 定义状态

确定我们要记录的”结果”是什么。

• 在网格路径问题中：dp[i][j] 表示从起点到达格子 (i, j) 的总路径数
• 在爬楼梯问题中：dp[n] 表示到达第 n 级台阶的方法数

2. 状态转移方程

找出现状和过去的关系。

// 网格路径问题
dp[i][j] = dp[i-1][j] + dp[i][j-1]

// 爬楼梯问题
dp[n] = dp[n-1] + dp[n-2]

3. 边界条件（初始化）

最基础、不用算就知道答案的情况。

// 网格路径问题
dp[0][j] = 1  // 第一行，只能一直往右
dp[i][0] = 1  // 第一列，只能一直往下

// 爬楼梯问题
dp[1] = 1  // 第1级台阶，1种方法
dp[2] = 2  // 第2级台阶，2种方法

代码实现

网格路径问题（Unique Paths）

def uniquePaths(m: int, n: int) -> int:
    """
    计算从左上角到右下角的不同路径数

    Args:
        m: 网格行数
        n: 网格列数

    Returns:
        不同路径的总数
    """
    # 创建 DP 表
    dp = [[0] * n for _ in range(m)]

    # 初始化边界
    for i in range(m):
        dp[i][0] = 1
    for j in range(n):
        dp[0][j] = 1

    # 状态转移
    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]

# 使用示例
print(uniquePaths(3, 7))  # 输出: 28

空间优化版本

def uniquePaths_optimized(m: int, n: int) -> int:
    """
    空间优化版本，只使用一维数组
    """
    dp = [1] * n

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

    return dp[n-1]

动态规划解题步骤

1. 定义状态 - 明确 dp[i] 或 dp[i][j] 代表什么
2. 找状态转移方程 - 确定状态之间的递推关系
3. 初始化 - 设置边界条件
4. 计算顺序 - 确定是从前往后还是从后往前
5. 返回结果 - 确定最终需要返回的是哪个状态

常见动态规划问题

问题类型	典型题目	状态定义
线性 DP	爬楼梯、打家劫舍	dp[i] 表示到达位置 i 的最优解
二维 DP	网格路径、最小路径和	dp[i][j] 表示到达 (i,j) 的最优解
区间 DP	矩阵链乘法	dp[i][j] 表示区间 [i,j] 的最优解
背包 DP	0-1背包、完全背包	dp[i][w] 表示前 i 个物品容量 w 的最大价值
树形 DP	树的最大独立集	在树上进行 DP

学习心得

1. 理解本质：DP 就是”带记忆的递归”，用空间换时间
2. 画表格：手动模拟 DP 表格的填充过程非常有帮助
3. 找规律：从简单情况开始，观察状态之间的关系
4. 多练习：DP 题目类型固定，多做题就能掌握套路

相关题目

• LeetCode 62. 不同路径
• LeetCode 63. 不同路径 II
• LeetCode 64. 最小路径和
• LeetCode 70. 爬楼梯
• LeetCode 198. 打家劫舍