本文介绍动态规划核心思想，通过存储子问题解避免重复计算，实现空间换时间。内容涵盖从暴力递归到迭代 DP 的演进，以斐波那契数列展示复杂度优化。讲解线性 DP 模型，包括爬楼梯和打家劫舍的状态定义、转移方程及初始化技巧。探讨背包模型，对比完全背包与 0/1 背包区别，通过零钱兑换和分割等和子集解析一维 DP 遍历方向。分析二维 DP 在网格路径和双序列匹配中的应用。提供完整 Java 代码及复杂度分析，总结 DP 解题四步法及常见误区，帮助掌握最佳实践。
回溯算法本质上是一种暴力的穷举搜索，它遍历了问题的所有可能性（状态空间树）。然而，在许多问题中，回溯搜索会产生大量的重叠子问题，导致计算资源的极度浪费。
动态规划（Dynamic Programming, DP） 并非一种具体的算法，而是一种数学优化的思维方式。它是一种通过将复杂问题分解为子问题，并存储子问题的解以避免重复计算的算法技术。它与分治法（Divide and Conquer）的区别在于：分治法的子问题通常是独立的（如归并排序），而动态规划的子问题是重叠的。
DP 的核心思想是空间换时间。通过维护一个表格（Table，通常是数组）来记录已经计算过的状态，将指数级的时间复杂度优化为多项式级（通常是线性或平方级）。
理解 DP 的最佳路径是从斐波那契数列（Fibonacci）开始。虽然这是一个简单的数学问题，但它完美展示了算法复杂度的演变。
斐波那契数列定义：f(n) = f(n-1) + f(n-2)。
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
分析：
该算法的执行流程是一棵二叉树。计算 f(20) 需要计算 f(19) 和 f(18)，而计算 f(19) 又需要计算 f(18) 和 f(17)。
f(18) 被重复计算了多次。随着 n 增大，重复计算呈指数级爆炸。O(2^n)。当 n=50 时，计算量将达到千万亿级，程序会超时。为了解决重复计算，我们可以引入一个'备忘录'（Memo），即一个数组或哈希表。每次计算 f(n) 前，先查表；计算完后，将结果存入表。
int[] memo;
public int fib(int n) {
memo = new int[n + 1];
return helper(n);
}
int helper(int n) {
if (n <= 1) return n;
// 查表：如果计算过，直接返回
if (memo[n] != 0) return memo[n];
// 如果没有计算过，计算并存表
memo[n] = helper(n - 1) + helper(n - 2);
return memo[n];
}
分析：
O(n)。空间复杂度 O(n)（递归栈 + 数组）。记忆化搜索依然保留了递归调用的栈开销。动态规划则是自底向上的迭代。不再需要递归函数，而是直接通过循环填充数组。
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 形态。它消除了递归栈的风险，且逻辑清晰。
观察转移方程 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[i] 的值通常仅依赖于 dp[i-1]、dp[i-2] 等前几个状态。
解决线性 DP 的关键在于下标对齐。需要明确 dp[i] 中的 i 到底代表什么，这直接决定了数组的大小、初始化的边界以及循环的起点。
题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶？
逻辑深度解析：
dp[i] 为 到达第 i 阶楼梯的方法总数。dp[n]。在 Java 数组中，要使下标 n 合法，数组长度必须至少为 n+1。因此声明 int[] dp = new int[n + 1]。其中 dp[0] 是占位符，无实际物理意义（或理解为站在地面，无需走动，意义不大）。dp[i] = dp[i-1] + dp[i-2]。dp[i] 需要依赖前两项。因此，i=1 和 i=2 不能通过方程计算（会造成下标越界或无意义），必须人为设定：
dp[1] = 1：到达第 1 阶只有 1 种方法（1）。dp[2] = 2：到达第 2 阶有 2 种方法（1+1 或 2）。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];
}
题目描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金
nums[i]，相邻的房屋装有防盗系统，不可同时被偷。求最高金额。
逻辑深度解析：
与爬楼梯不同，本题输入的是一个数组 nums，其下标从 0 到 n-1。
nums 的下标保持一致，定义 dp[i] 为 考虑前 i+1 间房屋（即下标范围 0…i）所能获得的最高金额。dp 数组长度设为 n 即可，下标范围 0…n-1 与 nums 完全对齐。nums[i] + dp[i-2]。dp[i-1]。dp[i] = max(dp[i-1], nums[i] + dp[i-2])。dp[0]：只有第 0 间房。必然偷。值 = nums[0]。dp[1]：有第 0、1 间房。不能同时偷，只能偷其中金额大的那间。值 = max(nums[0], nums[1])。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];
}
| 特征 | 爬楼梯 | 打家劫舍 |
|---|---|---|
| 输入形式 | 数字 n (代表第 1 到第 n 层) | 数组 nums (下标 0 到 n-1) |
| 状态定义 | dp[i] = 到达第 i 层 | dp[i] = 考虑下标 0…i 的房屋 |
| 数组大小 | n + 1 (为了能取到下标 n) | n (为了能取到下标 n-1) |
| 初始化项 | dp[1], dp[2] (物理意义上的前两步) | dp[0], dp[1] (数组的前两项) |
| 循环起点 | i = 3 | i = 2 |
| 最终结果 | dp[n] | dp[n-1] |
通过这两个例题可以看出，DP 数组的构建方式完全服务于状态的定义。
所以 打家劫舍 题目中也完全可以使用类似 爬楼梯 的定义方式。即使用 dp[n+1] 数组，其中 dp[i] 表示考虑前 i 间房屋（下标范围 0…i-1）所能获得的最高金额。这种方式更注重'前 0 间房屋'的边界（dp[0] = 0），最终结果为 dp[n]。
dp[i] = 考虑前 i 间房屋的最大金额。dp[i] = max(dp[i-1], nums[i-1] + dp[i-2])（注意 nums 下标调整为 i-1）。dp[0] = 0（无房屋）；dp[1] = nums[0]（只有第一间）。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 的一个特殊分支，其核心特征是：给定一组物品（具有价值与体积）和一个容器（有限容量），决策如何选择物品以达成目标。
最常见的两类背包模型是：
这两类问题在代码结构上极度相似，唯一的区别在于内层循环的遍历方向。理解这一点是掌握背包问题的关键。
题目描述：给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。每种硬币的数量是无限的。
逻辑深度解析：
dp[i] 表示凑齐金额 i 所需的最小硬币数量。1（当前这枚）加上'凑齐剩余金额 i-c 的最小硬币数'。
dp[i] = min(dp[i], dp[i-c] + 1)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];
}
题目描述：给你一个 只包含正整数 的 非空 数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
逻辑深度解析：
Target = Sum / 2。
问题转化为：能否装满容量为 Target 的背包？
由于每个数字只能用一次，这是标准的0/1 背包问题（每个物品不可重复使用）。dp[i] 表示容量为 i 的背包能否被恰好填满（boolean 类型）。dp[0] = true（空背包总是能'填满'0），其他 dp[j] = false。dp[j] 保持原值（即之前是否能填满 j，不受 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 的'子问题依赖'思想。如果没有这个，问题就无法分解为更小的子问题，导致无法逐步构建答案。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];
}
在将背包问题优化为一维 DP 数组后，完全背包和 0/1 背包在代码结构上高度相似，主要差异体现在物品的可重复性和内层循环的遍历方向上。这直接决定了状态更新的逻辑，避免了重复计算或非法重复使用物品。
||) 或 max/min 来合并'选/不选'的结果。如果顺序错乱，会导致物品被多次使用，违背问题约束。amount + 1），避免溢出或无效覆盖。二维动态规划的状态通常由两个变量 (i, j) 决定，状态转移方程往往涉及 dp[i-1][j]（上方）、dp[i][j-1]（左方）以及 dp[i-1][j-1]（左上方/对角线状态）。
二维 DP 主要考察两类模型：
dp[i][j] 往往表示'第一个序列的前 i 个'与'第二个序列的前 j 个'的关系。题目描述：一个机器人位于 m x n 网格的左上角。机器人每次只能 向下 或者 向右 移动一步。试图达到网格的右下角。问总共有多少条不同的路径？
逻辑解析：
dp[i][j] 表示从起点 (0, 0) 走到坐标 (i, j) 的路径总数。(i, j)。
(i-1, j)。(i, j-1)。dp[i][j] = dp[i-1][j] + dp[i][j-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];
}
这是二维 DP 中最经典、最具代表性的题目。理解了它，就理解了编辑距离、回文子序列等一系列困难题目。
题目描述：给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列，返回 0。 *子序列：不要求连续，但要求相对顺序一致。
逻辑解析：
dp[i][j] 表示 text1 的前 i 个字符（即 text1[0...i-1]）与 text2 的前 j 个字符（即 text2[0...j-1]）的最长公共子序列长度。
dp[0][0] 表示两个空串的 LCS，长度为 0。这样可以避免复杂的下标越界判断。text1 的第 i 个字符（索引 i-1）和 text2 的第 j 个字符（索引 j-1）：
c1 == c2)
既然这两个字符一样，那它们一定属于 LCS（最长公共子序列）的一部分。
LCS 长度 = 去掉这两个字符后的 LCS 长度 + 1。
dp[i][j] = dp[i-1][j-1] + 1。c1 != c2)
这两个字符不可能同时出现在 LCS 的末尾。LCS 要么继承自'text1 少一个字符'的结果，要么继承自'text2 少一个字符'的结果。取最大值。
dp[i][j] = max(dp[i-1][j], dp[i][j-1])。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];
}
网格路径 和 双序列匹配 两者的核心差异在于 状态定义的维度含义 以及 转移方程的触发条件。
(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）。| 特征 | 网格路径 (如 Unique Paths) | 双序列匹配 (如 LCS / Edit Distance) |
|---|---|---|
| 输入形式 | 矩阵 grid 或维度 m, n | 两个字符串 s1, s2 |
| 数组大小 | m × n | (m + 1) × (n + 1) |
| 下标含义 | 坐标 (i, j) | 长度 i (对应字符 s1[i-1]) |
| 状态依赖 | 上 (i-1)、左 (j-1) | 上、左、左上 (i-1, j-1) |
| 转移条件 | 无条件 (直接计算) | 字符相等/不等 (s1[i-1] == s2[j-1]) |
| 核心操作 | 加法 / Min / Max | Min / Max / +1 |
动态规划是算法中区分度较高的板块，其本质是将最优子结构与重叠子问题结合，通过填表法将指数级暴力搜索优化为多项式级迭代。掌握 DP 在于能够根据题意快速构建状态转移方程。
在面对 DP 问题时，通常可以通过以下流程分析问题：
dp 数组下标的物理含义。
dp[i] 通常表示'前 i 个元素'或'以第 i 个元素结尾'的最优解。dp[i][j] 表示'前 i 个物品在容量 j 下'的最优解（优化后为 dp[j]）。dp[i][j] 表示'序列 A 的前 i 个'与'序列 B 的前 j 个'的匹配结果。+1, max, min）。dp[0] 或 dp[1] 的物理意义是什么？（如爬楼梯 dp[1] = 1）。O(状态数量 × 单次转移耗时)。
O(N)。O(N × M)。O(N) 或 O(N^2)）。dp[i] 只依赖于 dp[i-1]（或 dp[i][j] 只依赖上一行），可以将空间维数降低一维（例如 O(N^2) → O(N)）。dp[i-1]、dp[i-2] 或 dp[j-coin] 越界。
i=2 开始），或者在循环内加 if (i >= coin) 判断。n + 1，下标 1 代表第 1 个元素，下标 0 代表空集/空串，这样能极大简化边界判断。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online