动态规划用数组存子问题解以避免重复计算，关键在明确定义状态、写出转移方程、按依赖顺序填数组，并注意边界、遍历方向、空间优化与调试技巧。

用数组实现动态规划的状态转移，核心是把每个子问题的解存进数组里，避免重复计算。关键在于明确状态定义、写出状态转移方程，并用数组按顺序填值。

明确状态定义，选对数组维度和下标含义

状态数组的每一项要对应一个具体子问题的最优解。比如求斐波那契第 n 项，就定义 dp[i] 表示第 i 项的值；求最长递增子序列时，dp[i] 常表示“以 nums[i] 结尾的最长递增子序列长度”。下标含义必须统一且可推导，不能模糊。

• 一维问题（如爬楼梯、最大子数组和）：通常用 dp[i] 表示前 i 个元素/到第 i 步时的最优解
• 二维问题（如编辑距离、最长公共子序列）：常用 dp[i][j] 表示字符串/数组前 i 和前 j 个字符对应的子问题解
• 注意边界：下标常从 0 或 1 开始，初始化时要把最基础的情况（如 dp[0]、dp[1] 或 dp[0][0]）设对

根据子问题依赖关系确定遍历顺序

状态转移方程右边的项必须在计算左边之前已被算出。这决定了数组填充的方向。

• 若 dp[i] = dp[i−1] + dp[i−2]，就要从小到大遍历 i（i = 2 到 n）
• 若 dp[i][j] = dp[i−1][j−1] + 1（当字符相等），则需按行主序或列主序，保证左上角已计算
• 有些问题需斜着遍历（如区间 DP），这时可用区间长度 len 作外层循环，再枚举起点 i

写出转移方程并用数组存中间结果

方程不是凭空来的，它来自对最后一步决策的分类讨论。写出来后，直接套进数组赋值即可。

• 例：背包问题中，dp[i][w] 表示前 i 个物品、容量为 w 时的最大价值。
  转移方程：dp[i][w] = max(dp[i−1][w], dp[i−1][w−weight[i]] + value[i])（选或不选第 i 个）
• 空间优化：若当前行只依赖上一行，可用滚动数组（两个一维数组或单数组倒序更新）节省空间
• 记录路径？可在更新 dp 同时用另一个数组（如 path[i] 或 choice[i][j]）记下决策来源，便于回溯

调试与验证中间结果的小技巧

数组本质是缓存，打印部分中间值能快速定位逻辑错误。

• 在循环中加条件输出：比如每 5 步 print(dp[i])，或只输出 dp[n//2]、dp[-1] 等关键位置
• 手动模拟小样例（如 n=4 的爬楼梯），对照数组每步填的值是否符合预期
• 检查越界：访问 dp[i−1] 前确认 i > 0；二维时注意 i−1 ≥ 0 且 j−1 ≥ 0