动态规划介绍

一、什么是动态规划

动态规划（Dynamic Programming，简称 DP）是一种 将复杂问题分解为若干子问题，通过保存子问题的解来避免重复计算 的算法思想。

它常用于 最优解问题（如最短路径、最大收益、最小代价等），核心思想是“状态转移 + 记忆化”。

动态规划适用于 具有重叠子问题 和 最优子结构 的问题。

---

二、动态规划的核心思想

通过记录子问题的最优解，逐步推导出原问题的最优解。

相比递归暴力搜索，动态规划避免了重复计算，时间复杂度大幅降低。

例如：斐波那契数列、背包问题、最长公共子序列、股票买卖问题等，都是典型的动态规划问题。

---

三、动态规划的五部曲

① 明确 dp 数组（表）及其含义

• 定义 dp[i] 或 dp[i][j] 的物理意义。
• 例如：dp[i] 表示“前 i 个物品的最大价值”；dp[i][j] 表示“字符串 A 的前 i 个字符与字符串 B 的前 j 个字符的最长公共子序列长度”。

② 确定状态转移方程

• 动态规划的核心。
• 找出当前状态与子状态之间的关系。
• 例如：dp[i] = max(dp[i-1], dp[i-2] + nums[i])（打家劫舍问题）。

③ 明确初始条件（边界条件）

• 动态规划需要从基础情况开始递推。
• 例如：dp[0] = nums[0], dp[1] = max(nums[0], nums[1])。

④ 确定遍历顺序

• 按照依赖关系确定遍历方向（自顶向下递归 + 记忆化，或自底向上递推）。
• 对二维 DP 问题，如背包问题，要考虑先遍历物品还是容量。

⑤ 举例推导验证

• 通过具体例子模拟 DP 数组的变化，验证状态转移是否正确。
• 帮助理解转移逻辑和遍历顺序。

---

四、动态规划的常见应用场景

1. 序列类问题

   • 最长上升子序列（LIS）
   • 最长公共子序列（LCS）
   • 编辑距离（Edit Distance）

2. 背包类问题

   • 0-1 背包、完全背包、多重背包
   • 股票买卖问题

3. 区间类问题

   • 戳气球、矩阵连乘、石子合并

4. 路径最优问题

   • 最短路径（Dijkstra、Floyd）
   • 最小路径和

---

五、示例：斐波那契数列（Fibonacci）

问题描述

计算第 n 个斐波那契数列的值。

状态定义

dp[i] 表示第 i 个斐波那契数。

状态转移方程

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

初始化

dp[0] = 0, dp[1] = 1

遍历顺序

从小到大递推 i。

完整代码示例

public int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

通过保存中间结果，时间复杂度从 O(2ⁿ) 降到 O(n)。

---

目录

• 动态规划介绍
• 多重背包