第1章：动态规划入门
1.1 动态规划的基本思想
动态规划，说白了就是一种「聪明的穷举」。我刚开始接触这个概念时，觉得它玄乎得很。后来做项目多了才发现，它其实就是把大问题拆成小问题，然后记住小问题的答案，避免重复计算。
动态规划有两个核心特征：最优子结构和重叠子问题。
最优子结构
什么叫最优子结构？简单说就是：一个问题的最优解，包含了其子问题的最优解。
举个例子。你想从北京坐火车到广州，中间经过武汉。如果你走的路线是最短的，那么从北京到武汉这一段，也一定是最短的。否则，你完全可以换一条更短的北京→武汉路线，让整体更短。这就是最优子结构。
我在项目中遇到过一个问题：要给一批订单分配生产线。每个订单可以选不同的机器，成本不同。我当时第一反应就是贪心，结果发现不行。后来用动态规划，就是因为这个问题天然具有最优子结构——前k个订单的最优分配，一定包含前k-1个订单的最优分配。
重叠子问题
重叠子问题，就是不同的「大问题」会用到同一个「小问题」的答案。
你想想看，斐波那契数列就是最典型的例子。计算F(5)需要F(4)和F(3)，计算F(4)又需要F(3)和F(2)。这里的F(3)被重复计算了两次。如果n很大，这种重复会爆炸。
动态规划的做法就是：把算过的结果存起来，下次直接用。这就是所谓的「记忆化搜索」或者「填表法」。
核心要点：动态规划 = 递归 + 记忆化。没有重叠子结构的问题，不适合用动态规划。
1.2 状态定义与状态转移方程
这是动态规划里最难的部分，也是最有意思的部分。我个人习惯把状态定义看作「给问题建模」。
状态定义
状态，就是你要用几个变量来描述当前的情况。比如0-1背包问题，我们需要知道：当前考虑到了第几个物品，以及背包还剩多少容量。所以状态就是 dp[i][j]，表示前i个物品，背包容量为j时的最大价值。
状态定义的好坏，直接决定了你能不能写出转移方程。我见过太多人卡在这一步。我的建议是：先想清楚你要记录哪些信息，然后再想这些信息怎么变化。
小技巧：状态定义时，尽量让状态「无后效性」——即当前状态一旦确定，后续决策只依赖于当前状态的值，而不依赖于它是怎么来的。
状态转移方程
状态转移方程，就是描述「从一个状态怎么走到下一个状态」的规则。说白了，就是递推公式。
还是拿0-1背包举例。对于第i个物品，你有两个选择：
- 不选：那么价值不变，容量不变，状态变成
dp[i-1][j] - 选：前提是容量够，价值增加
value[i]，容量减少weight[i]，状态变成dp[i-1][j-weight[i]] + value[i]
所以转移方程就是：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]) // 当 j >= weight[i]
dp[i][j] = dp[i-1][j] // 当 j < weight[i]嗯，这里要注意：边界条件。当i=0或j=0时，dp值都是0，因为没有物品或者没有容量。
1.3 经典案例：0-1背包问题
0-1背包是动态规划的「Hello World」。我当年面试的时候，几乎每家公司都会问这个。
问题描述：有N个物品，每个物品有重量w[i]和价值v[i]。你有一个容量为C的背包，问能装下的最大价值是多少？每个物品只能选一次（0或1次）。
直接上代码：
def knapsack_01(weights, values, capacity):
n = len(weights)
# dp[i][j] 表示前i个物品，容量j时的最大价值
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, capacity + 1):
if j >= weights[i-1]:
dp[i][j] = max(dp[i-1][j],
dp[i-1][j-weights[i-1]] + values[i-1])
else:
dp[i][j] = dp[i-1][j]
return dp[n][capacity]我曾经踩过的坑：一开始写0-1背包时，我用了二维数组，但没注意物品索引从0开始。结果dp[i-1]总是取错行。调试了半天才发现。后来我习惯把dp数组多开一行一列，用1-based索引，省心很多。
空间优化版本（一维数组）：
def knapsack_01_optimized(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
# 注意：必须倒序遍历容量
for j in range(capacity, weights[i] - 1, -1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity]为什么要倒序？因为一维数组里，dp[j-weights[i]] 必须是上一轮（没选当前物品）的值。如果正序遍历，它会被当前轮覆盖掉，相当于一个物品被选了多次——那就变成完全背包问题了。
1.4 最长公共子序列（LCS）
LCS是另一个经典问题。给定两个字符串，找出它们最长的公共子序列（不要求连续）。
状态定义：dp[i][j] 表示字符串A的前i个字符和字符串B的前j个字符的LCS长度。
转移方程：
- 如果
A[i-1] == B[j-1]，那么dp[i][j] = dp[i-1][j-1] + 1 - 否则，
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
代码实现：
def lcs(A, B):
m, n = len(A), len(B)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]我个人的经验：LCS的难点不在于写转移方程，而在于回溯出具体的子序列。如果你需要输出子序列本身，记得在填表时额外用一个数组记录路径（比如从哪个方向转移过来的）。
1.5 最短路径问题（Floyd-Warshall算法）
Floyd-Warshall算法解决的是多源最短路径问题——求任意两点之间的最短距离。
它的思想非常优雅：逐步允许经过更多的中间节点。
状态定义：dist[k][i][j] 表示只允许经过前k个节点（编号0到k-1）时，从i到j的最短距离。
转移方程：
dist[k][i][j] = min(dist[k-1][i][j], dist[k-1][i][k] + dist[k-1][k][j])说白了就是：要么不走第k个节点，要么走。取两者中较小的。
空间优化后，可以直接在原数组上操作：
def floyd_warshall(graph):
n = len(graph)
dist = [row[:] for row in graph] # 复制邻接矩阵
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist注意：Floyd-Warshall的时间复杂度是O(n³)，只适合节点数较少（比如几百以内）的图。节点数多的话，建议用Dijkstra（单源）或者Johnson算法。
知识体系总览
下面这张图总结了本章的核心内容：
动态规划的核心就三件事：定义好状态、写出转移方程、处理好边界。剩下的就是多练。我见过太多人一开始觉得难，但坚持做10道题之后，基本就能掌握套路了。
记住一句话：动态规划不是玄学，是结构化的穷举。你只要把状态空间想清楚，剩下的就是填表而已。