Java 动态规划实战：从递归优化到经典模型解析

分析：

• 剪枝：递归树中的重复分支被剪除。
• 复杂度：每个子问题只计算一次，总耗时 O(n)。空间复杂度 O(n)（递归栈 + 数组）。

1.3 动态规划

记忆化搜索依然保留了递归调用的栈开销。动态规划则是自底向上的迭代。不再需要递归函数，而是直接通过循环填充数组。

public int fib(int n) {
    if (n <= 1) return n;
    // 状态定义：dp[i] 表示第 i 个斐波那契数
    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];
}

分析： 这是标准的 DP 形态。它消除了递归栈的风险，且逻辑清晰。

1.4 空间优化

观察转移方程 dp[i] = dp[i-1] + dp[i-2]，可以发现：计算当前状态只依赖于前两个状态。因此，不需要维护整个数组，只需两个变量即可。

public int fib(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

分析： 空间复杂度降低至 O(1)。这种技巧在 DP 问题中非常通用。

二、线性 DP：一维状态链

线性 DP 是动态规划中最基础的模型。其特征是：问题可以被分解为线性排列的子问题，状态 dp[i] 的值通常仅依赖于 dp[i-1]、dp[i-2] 等前几个状态。

解决线性 DP 的关键在于下标对齐。需要明确 dp[i] 中的 i 到底代表什么，这直接决定了数组的大小、初始化的边界以及循环的起点。

2.1 实战例题：爬楼梯

题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？

逻辑深度解析：

1. 状态定义： 题目描述中的楼梯层数是 1 到 n。为了直观映射，我们定义 dp[i] 为 到达第 i 阶楼梯的方法总数。
2. 数组大小选择： 由于要计算的是第 n 阶，即需要访问 dp[n]。在 Java 数组中，要使下标 n 合法，数组长度必须至少为 n+1。因此声明 int[] dp = new int[n + 1]。其中 dp[0] 是占位符，无实际物理意义（或理解为站在地面，无需走动，意义不大）。
3. 推导转移方程： 到达第 i 阶只有两种可能：
   • 从第 i-1 阶向上爬 1 阶。
   • 从第 i-2 阶向上爬 2 阶。 因此：dp[i] = dp[i-1] + dp[i-2]。
4. 初始化与循环起点： 根据方程，计算 dp[i] 需要依赖前两项。因此，i=1 和 i=2 不能通过方程计算（会造成下标越界或无意义），必须人为设定：
   • dp[1] = 1：到达第 1 阶只有 1 种方法（1）。
   • dp[2] = 2：到达第 2 阶有 2 种方法（1+1 或 2）。
   • 循环起点：因为 1 和 2 已知，推导从第 3 阶开始，即 i = 3。

Java 代码：

public int climbStairs(int n) {
    // 边界条件：如果只有 1 阶或 2 阶，直接返回 n 即可，无需建表
    if (n <= 2) return n;
    // 数组大小：n + 1
    // 目的是为了让 dp[i] 直接对应'第 i 阶'，避免 i-1 的思维转换
    int[] dp = new int[n + 1];
    // 初始化
    dp[1] = 1; dp[2] = 2;
    // 状态转移
    // 从第 3 阶开始计算，一直计算到第 n 阶
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    // 返回第 n 阶的结果
    return dp[n];
}

2.2 实战例题：打家劫舍

题目描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金 nums[i]，相邻的房屋装有防盗系统，不可同时被偷。求最高金额。

逻辑深度解析：

与爬楼梯不同，本题输入的是一个数组 nums，其下标从 0 到 n-1。

1. 状态定义： 为了与输入数组 nums 的下标保持一致，定义 dp[i] 为 考虑前 i+1 间房屋（即下标范围 0…i）所能获得的最高金额。
2. 数组大小选择： 输入数组长度为 n，要计算的最终结果是考虑所有房屋（即下标 n-1）。因此 dp 数组长度设为 n 即可，下标范围 0…n-1 与 nums 完全对齐。
3. 推导转移方程： 对于下标为 i 的房屋，有两种决策：
   • 方案 A（偷第 i 间）：前提是第 i-1 间不能偷。那么最大金额 = 第 i 间的钱 + 考虑前 i-2 间房屋的最大金额。即 nums[i] + dp[i-2]。
   • 方案 B（不偷第 i 间）：那么最大金额 = 考虑前 i-1 间房屋的最大金额（即保持之前的最优解）。即 dp[i-1]。
   • 决策：取两者最大值。dp[i] = max(dp[i-1], nums[i] + dp[i-2])。
4. 初始化与循环起点： 方程中涉及 i-2，因此 i=0 和 i=1 必须单独初始化，防止越界：
   • dp[0]：只有第 0 间房。必然偷。值 = nums[0]。
   • dp[1]：有第 0、1 间房。不能同时偷，只能偷其中金额大的那间。值 = max(nums[0], nums[1])。
   • 循环起点：从下标 2 开始，即 i = 2。

Java 代码：

public int rob(int[] nums) {
    // 边界检查：空数组或长度为 0
    if (nums == null || nums.length == 0) return 0;
    // 只有一间房，直接偷
    if (nums.length == 1) return nums[0];
    int n = nums.length;
    // 数组大小：n
    // dp[i] 对应 nums[0...i] 的计算结果
    int[] dp = new int[n];
    // 初始化
    dp[0] = nums[0];
    // 对于第二间房，最大收益是两间房中较大的那个，而不是 nums[1]
    dp[1] = Math.max(nums[0], nums[1]);
    // 状态转移
    // 从下标 2 开始遍历到 n-1
    for (int i = 2; i < n; i++) {
        // 偷 i: nums[i] + dp[i-2]
        // 不偷 i: dp[i-1]
        dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
    }
    // 最终状态存储在数组最后一个位置
    return dp[n - 1];
}

2.3 如何确定数组大小与循环起点？

通过这两个例题可以看出，DP 数组的构建方式完全服务于状态的定义。

所以 打家劫舍 题目中也完全可以使用类似 爬楼梯 的定义方式。即使用 dp[n+1] 数组，其中 dp[i] 表示考虑前 i 间房屋（下标范围 0…i-1）所能获得的最高金额。这种方式更注重'前 0 间房屋'的边界（dp[0] = 0），最终结果为 dp[n]。

1. 状态定义：dp[i] = 考虑前 i 间房屋的最大金额。
2. 转移方程：dp[i] = max(dp[i-1], nums[i-1] + dp[i-2])（注意 nums 下标调整为 i-1）。
3. 初始化：dp[0] = 0（无房屋）；dp[1] = nums[0]（只有第一间）。
4. 循环起点：从 i = 2 开始。

Java 代码

public int rob(int[] nums) {
    // 边界检查
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length;
    if (n == 1) return nums[0];
    // 数组大小：n + 1
    int[] dp = new int[n + 1];
    // 初始化
    dp[0] = 0; // 前 0 间房屋
    dp[1] = nums[0]; // 前 1 间房屋
    // 状态转移
    for (int i = 2; i <= n; i++) {
        // 偷第 i-1 间：nums[i-1] + dp[i-2]
        // 不偷：dp[i-1]
        dp[i] = Math.max(dp[i - 1], nums[i - 1] + dp[i - 2]);
    }
    // 最终结果：前 n 间房屋
    return dp[n];
}

三、背包模型：组合与最值

背包问题（Knapsack Problem）是线性 DP 的一个特殊分支，其核心特征是：给定一组物品（具有价值与体积）和一个容器（有限容量），决策如何选择物品以达成目标。

最常见的两类背包模型是：

1. 完全背包：每个物品可以被选择无限次。
2. 0/1 背包：每个物品只能被选择一次（要么选，要么不选）。

这两类问题在代码结构上极度相似，唯一的区别在于内层循环的遍历方向。理解这一点是掌握背包问题的关键。

3.1 实战例题：零钱兑换（完全背包求最值）

题目描述：给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。每种硬币的数量是无限的。

逻辑深度解析：

1. 模型识别： 硬币数量无限，意味着可以重复选择同一个面额。这是一个标准的完全背包问题。
2. 状态定义： dp[i] 表示凑齐金额 i 所需的最小硬币数量。
3. 状态转移方程： 对于金额 i，可以遍历所有硬币面额 c。 如果我们选择了面额 c，那么当前的硬币数就是 1（当前这枚）加上'凑齐剩余金额 i-c 的最小硬币数'。 dp[i] = min(dp[i], dp[i-c] + 1)
4. 初始化策略（求最小值的陷阱）：
   • dp[0] = 0：凑齐 0 元不需要硬币。
   • dp[1…amount]：由于我们在方程中使用了 Math.min，如果初始化为 0，所有结果都会被 0 覆盖。因此必须初始化为一个无效的大数值。
   • 注意：不要使用 Integer.MAX_VALUE，因为 dp[i-c] + 1 可能会导致整型溢出变成负数。推荐使用 amount + 1（即使全是 1 元硬币，数量也不会超过 amount，所以 amount + 1 等同于无穷大）。

Java 代码：

public int coinChange(int[] coins, int amount) {
    // 定义 DP 数组
    // 长度设为 amount + 1，保证下标能取到 amount
    int[] dp = new int[amount + 1];
    // 初始化
    // 使用 amount + 1 作为'无穷大'标记
    int max = amount + 1;
    Arrays.fill(dp, max);
    dp[0] = 0;
    // 状态转移
    // 外层循环：遍历所有可能的金额（背包容量）
    for (int i = 1; i <= amount; i++) {
        // 内层循环：遍历所有硬币（物品）
        for (int coin : coins) {
            // 只有当当前金额 i 大于等于硬币面额 coin 时，才能使用该硬币
            if (i >= coin) {
                // 核心方程：尝试放入 coin，看是否能使总数量变小
                // dp[i - coin] 是在当前层或之前层计算过的结果 0 <= i - coin <= i
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    // 结果校验
    // 如果 dp[amount] 仍然是初始值，说明无法凑出
    return dp[amount] > amount ? -1 : dp[amount];
}

3.2 实战例题：分割等和子集（0/1 背包存在性问题）

题目描述：给你一个 只包含正整数 的 非空 数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

逻辑深度解析：

1. 问题转化： '分割成两个相等子集'等价于'从数组中选出若干个数，使其和恰好等于总和的一半'。 设 Target = Sum / 2。 问题转化为：能否装满容量为 Target 的背包？ 由于每个数字只能用一次，这是标准的0/1 背包问题（每个物品不可重复使用）。
2. 状态定义：
   • dp[i] 表示容量为 i 的背包能否被恰好填满（boolean 类型）。
   • 初始时，dp[0] = true（空背包总是能'填满'0），其他 dp[j] = false。
3. 核心难点：转移方程的推导与遍历顺序
   • 转移方程的由来：
     • 对于每个数字 num，需要决定是否将其放入背包（容量 j）。
     • 如果不放 num：dp[j] 保持原值（即之前是否能填满 j，不受 num 影响）。
     • 如果放 num：前提是 j >= num（容量足够），则问题退化为'能否用之前的数字填满 j-num 的容量'，然后再加上 num 就正好填满 j。所以，这里需要用到 dp[j-num] —— 如果 dp[j-num] 为 true，说明之前能填满 j-num，现在加上 num 就能填满 j。
     • 综合决策：只要'不放'或'放'两种方式中任意一种可行，就设 dp[j] = true。因此，方程是 dp[j] = dp[j] || dp[j - num]（如果 j >= num）。
     • 为什么需要 dp[j-num]？因为这是'决策的核心'——它代表了'减去当前物品后'的子问题结果，体现了 DP 的'子问题依赖'思想。如果没有这个，问题就无法分解为更小的子问题，导致无法逐步构建答案。
   • 一维数组的遍历顺序（为什么从大到小）：
     • 在 0/1 背包中，内层循环必须从大到小遍历（从 target 到 num）。
     • 原因推导：
       • 正序遍历（从小到大）：计算 dp[j] 时，需要用到 dp[j-num]，但如果从左往右，dp[j-num] 可能已经被当前 num 更新过（相当于重复使用了 num），违背 0/1 原则（每个数字只能用一次）。
       • 示例：假设 num=3，target=6。从小到大：先更新 dp[3] = true（放 3），然后到 dp[6] 时，用 dp[6-3]=dp[3]（已包含 3），相当于用了两次 3，错误地认为能填满 6（3+3）。
       • 反序遍历（从大到小）：计算 dp[j] 时，dp[j-num] 还是'之前的状态'（未被当前 num 更新），确保 num 只被考虑一次。
       • 示例：从大到小，先更新 dp[6] 用 dp[3]（初始 false，不更新），然后更新 dp[3] 用 dp[0]=true → dp[3]=true。现在 dp[6] 仍 false（因为没其他数字支持第二次 3）。
     • 如果是完全背包（无限使用，如零钱兑换），则用正序遍历，以允许重复使用物品。

Java 代码：

public boolean canPartition(int[] nums) {
    // 预处理：计算总和
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    // 如果总和是奇数，无法平分，直接返回 false
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    // 定义 DP 数组
    // dp[j] 表示是否能凑出和为 j
    boolean[] dp = new boolean[target + 1];
    // 初始化
    dp[0] = true; // 容量为 0 时，不选任何元素即为满，为 true
    // 状态转移
    // 外层循环：遍历物品（数字）
    for (int num : nums) {
        // 内层循环：遍历背包容量；必须从大到小遍历 (target -> num)
        for (int i = target; i >= num; i--) {
            // 如果不放入 num：状态保持 dp[i]
            // 如果放入 num：状态取决于 dp[i - num]
            dp[i] = dp[i] || dp[i - num];
        }
    }
    return dp[target];
}

3.3 总结：完全背包 vs 0/1 背包

在将背包问题优化为一维 DP 数组后，完全背包和 0/1 背包在代码结构上高度相似，主要差异体现在物品的可重复性和内层循环的遍历方向上。这直接决定了状态更新的逻辑，避免了重复计算或非法重复使用物品。

• 物品限制与适用场景：
  • 0/1 背包：每个物品（数字/硬币）只能选择一次，适合'一次性决策'的问题，如'分割等和子集'（LC 416），本质上是判断是否存在子集和等于目标值。
  • 完全背包：每个物品可以无限重复选择，适合'可复用资源'的问题，如'零钱兑换'（LC 322），本质上是求最小/最大/组合数等优化值。
• 背包容量循环方向：
  • 0/1 背包：从大到小遍历（target 到 num），以确保每个物品只被考虑一次。反序防止当前物品的更新影响后续决策，引用的是'未更新前的状态'（相当于上一层的结果）。
  • 完全背包：从小到大遍历（num 到 target），允许当前物品的更新被后续容量复用，引用的是'当前层已更新的状态'，从而实现无限重复选择。
• 物理含义与注意事项：
  • 0/1 背包：强调 互斥决策，转移时使用或操作 (||) 或 max/min 来合并'选/不选'的结果。如果顺序错乱，会导致物品被多次使用，违背问题约束。
  • 完全背包：强调 累积优化，转移时直接覆盖更新，允许重复累加。如果是求最小值（如硬币个数），需小心初始化为无效大值（如 amount + 1），避免溢出或无效覆盖。

四、二维 DP：网格与双序列

二维动态规划的状态通常由两个变量 (i, j) 决定，状态转移方程往往涉及 dp[i-1][j]（上方）、dp[i][j-1]（左方）以及 dp[i-1][j-1]（左上方/对角线状态）。

二维 DP 主要考察两类模型：

1. 网格图模型（Grid）：在一个矩阵上移动，求路径数或最小路径和。重点在于边界初始化。
2. 双序列模型（Sequence）：比较两个字符串或数组，求最长公共子序列（LCS）、编辑距离等。重点在于状态 dp[i][j] 往往表示'第一个序列的前 i 个'与'第二个序列的前 j 个'的关系。

4.1 网格路径模型：不同路径

题目描述：一个机器人位于 m x n 网格的左上角。机器人每次只能 向下 或者 向右 移动一步。试图达到网格的右下角。问总共有多少条不同的路径？

逻辑解析：

1. 状态定义： dp[i][j] 表示从起点 (0, 0) 走到坐标 (i, j) 的路径总数。
2. 转移方程（加法原理）： 机器人只能通过'向下'或'向右'到达 (i, j)。
   • 如果是'向下'走一步到达，说明上一步在 (i-1, j)。
   • 如果是'向右'走一步到达，说明上一步在 (i, j-1)。
   • 因此：dp[i][j] = dp[i-1][j] + dp[i][j-1]。
3. 初始化（边界陷阱）： 网格类 DP 最容易出错的地方在于第一行和第一列。
   • 第一行：只能一直向右走，无法从上面下来，路径固定。因此第一行所有格子的路径数都是 1。
   • 第一列：只能一直向下走，无法从左边过来，路径固定。因此第一列所有格子的路径数都是 1。

Java 代码：

public int uniquePaths(int m, int n) {
    // 定义二维 DP 数组
    int[][] dp = new int[m][n];
    // 初始化
    // 第一列全为 1
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    // 第一行全为 1
    for (int j = 0; j < n; j++) {
        dp[0][j] = 1;
    }
    // 填充中间网格
    // 从 (1, 1) 开始，因为 (0, x) 和 (x, 0) 已经初始化
    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];
}

空间优化（滚动数组原理）： 在计算 dp[i][j] 时，只需要'上一行'的数据和'当前行左边'的数据。因此，可以将二维压缩为一维（只保留一行的空间，通过'滚动更新'模拟多行计算，复用数组空间以降低复杂度到 O(n)）。 设 dp[j] 为当前行第 j 列的值。

• 更新前，dp[j] 存储的是上一行的值（等价于 dp[i-1][j]）。
• 更新时，dp[j-1] 存储的是当前行刚刚更新过的左边的值（等价于 dp[i][j-1]）。
• 方程变为：dp[j] = dp[j] (旧) + dp[j-1] (新)。

public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    // 初始化第一行，全为 1
    Arrays.fill(dp, 1);
    // 从第二行开始遍历
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            // dp[j] (新值) = dp[j] (上一行的旧值) + dp[j-1] (当前行左边的新值)
            dp[j] += dp[j - 1];
        }
    }
    return dp[n - 1];
}

4.2 双序列模型：最长公共子序列

这是二维 DP 中最经典、最具代表性的题目。理解了它，就理解了编辑距离、回文子序列等一系列困难题目。

题目描述：给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列，返回 0。 *子序列：不要求连续，但要求相对顺序一致。

逻辑解析：

1. 状态定义： 定义 dp[i][j] 表示 text1 的前 i 个字符（即 text1[0...i-1]）与 text2 的前 j 个字符（即 text2[0...j-1]）的最长公共子序列长度。
   • 为什么要用'前 i 个'而不是'索引 i'？
   • 为了方便处理空字符串的情况。dp[0][0] 表示两个空串的 LCS，长度为 0。这样可以避免复杂的下标越界判断。
2. 状态转移： 考察 text1 的第 i 个字符（索引 i-1）和 text2 的第 j 个字符（索引 j-1）：
   • 情况 A：字符相等 (c1 == c2) 既然这两个字符一样，那它们一定属于 LCS（最长公共子序列）的一部分。 LCS 长度 = 去掉这两个字符后的 LCS 长度 + 1。 dp[i][j] = dp[i-1][j-1] + 1。
   • 情况 B：字符不等 (c1 != c2) 这两个字符不可能同时出现在 LCS 的末尾。LCS 要么继承自'text1 少一个字符'的结果，要么继承自'text2 少一个字符'的结果。取最大值。 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
3. 表格填充方向： 由于 dp[i][j] 依赖于左上 (i-1, j-1)、上 (i-1, j)、左 (i, j-1)，因此从左到右、从上到下遍历即可。

Java 代码：

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length();
    int n = text2.length();
    // dp[i][j] 对应 text1[0...i-1] 和 text2[0...j-1]
    // 大小设为 (m+1) x (n+1) 处理空串边界
    int[][] dp = new int[m + 1][n + 1];
    // i 和 j 从 1 开始，代表'第 1 个字符'
    for (int i = 1; i <= m; i++) {
        // 获取 text1 的字符，注意索引要 -1
        char c1 = text1.charAt(i - 1);
        for (int j = 1; j <= n; j++) {
            char c2 = text2.charAt(j - 1);
            if (c1 == c2) {
                // 字符匹配：继承左上方状态 + 1
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                // 字符不匹配：继承左方或上方的最大值
                // 意味着丢弃 c1 或者丢弃 c2，看谁剩下的 LCS 更长
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

4.3 总结：网格模型 vs 双序列模型

网格路径 和 双序列匹配 两者的核心差异在于 状态定义的维度含义 以及 转移方程的触发条件。

• 物理含义与状态定义：
  • 网格模型：状态 (i, j) 对应几何坐标。 dp[i][j] 表示到达该坐标点的路径数或最小代价。通常直接在 m × n 的数组上操作。
  • 双序列模型：状态 (i, j) 对应两个序列的前缀长度。 dp[i][j] 表示'序列 A 的前 i 个字符'与'序列 B 的前 j 个字符'的处理结果。为了处理空串情况，数组通常声明为 (m+1) × (n+1)。
• 转移逻辑与依赖方向：
  • 网格模型：转移通常是无条件的，直接依赖于 上方 (i-1, j) 和 左方 (i, j-1) 的累加或最值。
  • 双序列模型：转移是有条件的，依赖于当前字符是否匹配 (s1[i-1] == s2[j-1])。
    • 匹配时：通常继承 左上方 (i-1, j-1) 的状态（如 LCS +1）。
    • 不匹配时：通常继承 上方 或 左方 的最值（如 LCS 取 max）。
• 初始化：
  • 网格模型：第一行和第一列通常初始化为 1（代表只有一条直路）或累加值。
  • 双序列模型：第 0 行和第 0 列代表'空串'参与运算。对于 LCS 问题初始化为 0；对于编辑距离问题，初始化为索引值 i 或 j（代表删除/插入操作数）。

五、总结与最佳实践

动态规划是算法中区分度较高的板块，其本质是将最优子结构与重叠子问题结合，通过填表法将指数级暴力搜索优化为多项式级迭代。掌握 DP 在于能够根据题意快速构建状态转移方程。

5.1 DP 解题的四步

在面对 DP 问题时，通常可以通过以下流程分析问题：

1. 定义状态： 明确 dp 数组下标的物理含义。
   • 线性问题： dp[i] 通常表示'前 i 个元素'或'以第 i 个元素结尾'的最优解。
   • 背包问题： dp[i][j] 表示'前 i 个物品在容量 j 下'的最优解（优化后为 dp[j]）。
   • 双序列问题： dp[i][j] 表示'序列 A 的前 i 个'与'序列 B 的前 j 个'的匹配结果。
2. 推导方程： 思考'当前状态'是如何由'之前的状态'推导出来的。
   • 最后一步法：假设已经完成了前 i-1 步，第 i 步有哪些选择（选/不选、替换/删除）？
   • 操作映射：将题目中的操作（如'爬一步'、'偷这间'、'放入背包'）转化为数学运算（+1, max, min）。
3. 初始化： 处理边界条件，防止数组越界。
   • 逻辑边界： dp[0] 或 dp[1] 的物理意义是什么？（如爬楼梯 dp[1] = 1）。
   • 计算边界：求最小值时初始化为无穷大（如零钱兑换），求最大值时初始化为 0 或负无穷。
4. 确定遍历顺序：
   • 普通 DP：通常从左到右，从小到大。
   • 0/1 背包（一维优化）：内层循环必须从大到小（防止重复使用物品）。
   • 完全背包（一维优化）：内层循环必须从小到大（允许重复使用物品）。

5.2 复杂度分析

• 时间复杂度：O(状态数量 × 单次转移耗时)。
  • 线性 DP： O(N)。
  • 背包/双序列/网格 DP： O(N × M)。
• 空间复杂度：
  • 基础解法：与状态表大小一致（ O(N) 或 O(N^2)）。
  • 滚动数组优化：如果状态 dp[i] 只依赖于 dp[i-1]（或 dp[i][j] 只依赖上一行），可以将空间维数降低一维（例如 O(N^2) → O(N)）。

5.3 常见误区

1. 数组越界： DP 代码最常见的 Bug 是 dp[i-1]、dp[i-2] 或 dp[j-coin] 越界。
   • 对策：根据转移方程需要的 offset（偏移量），设定循环的起始点（如从 i=2 开始），或者在循环内加 if (i >= coin) 判断。
2. 状态定义的偏差： '第 i 个' vs '索引 i' 的坑。
   • 建议：涉及'前 i 个'或双序列问题时，数组开 n + 1，下标 1 代表第 1 个元素，下标 0 代表空集/空串，这样能极大简化边界判断。