动态规划：从思想到实战
动态规划，简称 DP，是算法领域的一块硬骨头。说实话，我刚开始学的时候也觉得这东西玄乎得很。后来在项目中做路径规划、资源分配，才慢慢摸到门道。说白了，动态规划就是一种「聪明的穷举」——把大问题拆成小问题，记住小问题的答案，避免重复计算。
动态规划的核心思想
动态规划有三个关键要素：最优子结构、重叠子问题和状态转移方程。
- 最优子结构：大问题的最优解，包含子问题的最优解。比如你从北京到上海的最短路径，肯定包含中间某个城市到上海的最短路径。
- 重叠子问题：不同的决策路径会走到同一个子问题上。如果每次都要重新算，那就太傻了。
- 状态转移方程：这是 DP 的灵魂。它描述了如何从子问题的解推导出当前问题的解。
我习惯用「填表法」来理解 DP。先画一张表，行和列代表不同的状态，然后一行一行、一列一列地把表填满。表填完了，答案也就出来了。
核心口诀：定义状态 → 写出转移方程 → 初始化边界 → 按顺序填表 → 返回结果。
0-1 背包问题
0-1 背包是 DP 的经典入门题。题目是这样的：有一个容量为 W 的背包，有 n 个物品，每个物品有重量 w[i] 和价值 v[i]。每个物品要么拿（1），要么不拿（0），问能装的最大价值是多少。
状态定义很简单：dp[i][j] 表示前 i 个物品中，选出总重量不超过 j 的最大价值。
转移方程：
if (j < w[i])
dp[i][j] = dp[i-1][j]; // 装不下，只能不拿
else
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]); // 不拿 vs 拿我在项目中做过一个资源调度模块，本质上就是 0-1 背包。当时有个坑：物品的重量和价值都是浮点数，直接当索引用不行。我的做法是统一乘以 100 取整，再用整数 DP。嗯，这里要注意精度问题。
空间优化技巧：观察转移方程，发现 dp[i] 只依赖 dp[i-1]。所以可以用一维数组，但内层循环要倒着遍历，防止覆盖。
完全背包问题
完全背包和 0-1 背包的区别在于：每个物品可以拿无限次。你想想看，这会导致什么变化？
状态定义不变：dp[i][j] 还是前 i 个物品，重量不超过 j 的最大价值。但转移方程变了：
if (j < w[i])
dp[i][j] = dp[i-1][j];
else
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i]); // 注意这里是 dp[i] 不是 dp[i-1]区别就在 dp[i][j-w[i]] 上。它表示：我决定再拿一个当前物品，但之前可能已经拿过这个物品了。所以是同一行内向左看，而不是上一行。
空间优化时，内层循环要正着遍历。为什么？因为我们需要用到当前行已经更新过的值。我曾经在面试时被问到这个问题，一时没转过弯来，后来自己画了张表才彻底明白。
注意：0-1 背包和完全背包的代码几乎一样，就差了内层循环的方向。面试时一定要说清楚为什么方向不同，否则面试官会觉得你只是背代码。
最长公共子序列（LCS）
LCS 是字符串 DP 的典型代表。给定两个字符串 s1 和 s2，找出它们的最长公共子序列的长度。注意，子序列不要求连续，但顺序必须一致。
状态定义：dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的 LCS 长度。
转移方程：
if (s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);这个方程很直观：如果当前字符相等，那就在之前的基础上加 1；如果不相等，那就取「丢掉 s1 的一个字符」和「丢掉 s2 的一个字符」中的较大值。
我记得有一次做代码差异对比工具，核心算法就是 LCS。当时还扩展了一下，输出具体的子序列内容，而不仅仅是长度。做法是在填表的同时记录路径，最后回溯。
最短编辑距离（Levenshtein Distance）
编辑距离衡量的是把一个字符串变成另一个字符串所需的最少操作次数。操作有三种：插入、删除、替换。
状态定义：dp[i][j] 表示把 s1 的前 i 个字符变成 s2 的前 j 个字符所需的最少操作数。
转移方程：
if (s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1]; // 字符相同，不需要操作
else
dp[i][j] = min(
dp[i-1][j] + 1, // 删除 s1[i-1]
dp[i][j-1] + 1, // 在 s1 中插入 s2[j-1]
dp[i-1][j-1] + 1 // 替换 s1[i-1] 为 s2[j-1]
);边界条件：dp[i][0] = i（删除所有字符），dp[0][j] = j（插入所有字符）。
这个算法在拼写检查、DNA 序列比对中都有应用。我曾经在项目中用它做模糊匹配，效果还不错。不过要注意，编辑距离对长字符串的计算开销比较大，可以考虑用滚动数组优化空间。
知识体系总览
下面这张图总结了本章的核心内容，方便你对照复习。
避坑指南
动态规划虽然强大，但用起来有几个容易踩的坑：
- 状态定义不清晰：我见过很多人一上来就写转移方程，结果写到一半发现状态定义有问题，推不下去。我的建议是：先花 5 分钟把状态定义写清楚，想明白 dp[i][j] 到底代表什么。
- 边界条件遗漏：比如 dp[0][j] 和 dp[i][0] 的初始化。我曾经在 LCS 的代码里忘了处理空字符串的情况，结果数组越界，查了半天 bug。
- 循环顺序搞反：0-1 背包和完全背包的代码几乎一样，就差了内层循环的方向。面试时一定要说清楚为什么方向不同。
- 空间优化后丢失信息：用一维数组优化空间后，如果还需要回溯路径，那就得额外记录决策信息。我一般会保留二维数组，除非内存真的不够用。
我的习惯：刚开始学 DP 时，先用二维数组把表填出来，确保逻辑正确。然后再考虑空间优化。这样不容易出错，也方便调试。
动态规划不是一蹴而就的。我当年也是刷了几十道题，才慢慢找到感觉。你只要把背包、LCS、编辑距离这几个经典问题吃透，后面再遇到 DP 题，心里就有底了。
公众号:蓝海资料掘金营，微信 deep3321