动态规划

一、直观理解：把大决策拆成互相嵌套的小决策

动态规划（Dynamic Programming, DP）可以理解为：如果一个大问题可以分成若干阶段，而且每个阶段的最优选择只依赖于「当前状态」而不必记住全部历史细节，那么就可以从最简单的子问题一层层推出整体最优。

想象你从城市 $A$ 开车到城市 $E$ ，中间可经过 $B$ 、 $C$ 、 $D$ 等节点。与其枚举所有完整路线，不如问：

若我已经到达某个中间城市，从这里到终点的最短剩余路程是多少？

一旦每个「中间城市」的最优剩余路程都算出来了，整条最短路径也就确定了。这就是「最优子结构」：大问题的最优解，由子问题的最优解拼接而成。

再看背包：在容量有限时挑选物品。问「容量为 $w$ 、只考虑前 $i$ 件物品时的最大价值」比直接枚举 $2^n$ 种取舍容易得多，因为答案可以从「前 $i-1$ 件」的结果递推得到。

动态规划不是某一种固定公式，而是一种利用阶段与状态做精确递推的建模思路。它与贪心的区别在于：贪心只看局部眼前最优，DP 会系统比较所有相关子问题。

二、适用场景与优缺点

类型	说明
适用场景	多阶段决策（生产计划按天、路径按站、资源按层分配）；具有最优子结构与（通常）无后效性；状态可用有限维离散量描述；组合优化中规模允许状态压缩的背包、最短路 DAG、编辑距离、库存多期模型等。
核心优点	在状态定义正确时给出精确最优；避免重复计算子问题；复杂度通常可明确写出；结果可回溯得到完整决策序列。
局限与缺点	状态设计不好会维度爆炸（维数灾难）；连续状态需离散化，带来误差；无后效性不满足时不能直接套；实现细节（边界、下标、初始化）易错。

使用 DP 前通常需要确认：

能否把问题划分成有序阶段（时间、位置、物品编号等）；
能否用紧凑的状态概括「对未来决策有影响的全部信息」；
状态转移是否只依赖更「小」的子问题；
状态总数 $\times$ 转移代价是否在可接受范围内；
是否需要同时输出最优值与最优策略。

若阶段结构不明显，或状态必须记住很长的历史路径，可能更适合整数规划、图算法或启发式搜索。

三、核心原理：阶段、状态、决策与转移

标准 DP 建模包含四个要素。

1. 阶段（Stage）

按自然顺序把过程切开，例如第 $k$ 天、第 $i$ 件物品、到达第 $t$ 个站点。阶段给出递推方向。

2. 状态（State）

状态 $s$ 是对「当前局势」的充分统计。例如：

背包：(已考虑物品数 i, 已用容量 w)；
最短路 DAG：节点 u；
库存：(时期 t, 库存水平 I)。

无后效性要求：给定当前状态，未来的最优与如何到达该状态无关。

3. 决策与转移（Decision & Transition）

在状态 $s$ 采取决策 $a$ 后进入状态 $s'$ ，并产生阶段费用/收益 $c(s,a)$ 。贝尔曼最优性方程（以最小化为例）写作：

V(s)=\min_{a\in A(s)}\Bigl\{c(s,a)+V\bigl(s'(s,a)\bigr)\Bigr\}

$V(s)$ 表示从状态 $s$ 出发到过程结束的最优总代价。边界状态给出 $V$ 的初值，例如终点 $V(s_{\text{end}})=0$ ，或非法状态 $V=\infty$ 。

4. 计算顺序与回溯

逆序 DP：从终点向起点递推（适合已知终点代价）；
顺序 DP：从小规模子问题推到大规模（背包常用）；
记忆化搜索：递归 + 缓存，本质仍是 DP。

求出最优值后，记录每个状态的最优决策，从起点沿决策指针回溯，得到完整方案。

经典例子：0-1 背包

$n$ 件物品，容量 $W$ ，第 $i$ 件重量 $w_i$ 、价值 $v_i$ 。令 $f(i,c)$ 为前 $i$ 件、容量 $c$ 时的最大价值：

f(i,c)=\max\bigl\{f(i-1,c),\; f(i-1,c-w_i)+v_i\bigr\} \quad (c\ge w_i)

边界 $f(0,\cdot)=0$ 。一维滚动优化后常用：

\text{对 } i=1..n,\; \text{对 } c=W..w_i:\; dp[c]=\max(dp[c],\, dp[c-w_i]+v_i)

注意内层容量必须逆序，以免同一件物品被重复放入。

四、关键决策：状态怎么设、表怎么填

1. 状态是否充分又不过大

状态必须包含所有影响未来收益的信息，但每多一维，复杂度往往乘上该维取值数。建模竞赛中常见技巧：

用「差分 / 相对量」代替绝对量；
按价值或容量做有界离散；
只保留帕累托前沿（多目标 DP）。

2. 初始化与不可行标记

最小化问题常用 $+\infty$ 表示不可达，最大化用 $-\infty$ 或 $0$ （视是否允许「什么都不做」）。初始化错误会导致整张表被污染。

3. 与最短路、整数规划的关系

许多 DP 等价于 DAG 上的最短/最长路；
某些 DP 可用自动生成的网络流或 MILP 表达，但 DP 实现往往更直接；
若状态空间巨大而约束好写，可改用 intlinprog。

4. 何时不该用 DP

转移依赖「未来信息」、必须枚举指数级子集且无法压缩、或连续高维状态无法合理网格化时，应换方法。

五、MATLAB 示例

下面用 0-1 背包演示顺序 DP，并回溯选出的物品。

% 0-1 背包：容量 W，n 件物品
W = 10;
w = [2, 3, 4, 5, 5];   % 重量
v = [3, 4, 5, 8, 9];   % 价值
n = numel(w);

% dp(c+1) 表示容量为 c 时的最大价值（MATLAB 下标从 1）
dp = zeros(1, W + 1);
% choice{c+1} 记录达到该容量最优时最后放入的物品编号
lastItem = zeros(1, W + 1);

for i = 1:n
    for c = W:-1:w(i)
        cand = dp(c - w(i) + 1) + v(i);
        if cand > dp(c + 1)
            dp(c + 1) = cand;
            lastItem(c + 1) = i;
        end
    end
end

bestValue = dp(W + 1);
fprintf("最大价值 = %g\n", bestValue);

% 回溯：利用一维 DP 的 lastItem 不够稳健时，改用二维表
dp2 = zeros(n + 1, W + 1);
for i = 1:n
    for c = 0:W
        dp2(i + 1, c + 1) = dp2(i, c + 1); % 不选 i
        if c >= w(i)
            dp2(i + 1, c + 1) = max(dp2(i + 1, c + 1), ...
                dp2(i, c - w(i) + 1) + v(i));
        end
    end
end

selected = false(1, n);
c = W;
for i = n:-1:1
    if dp2(i + 1, c + 1) ~= dp2(i, c + 1)
        selected(i) = true;
        c = c - w(i);
    end
end

disp("选中物品编号：");
disp(find(selected));
disp("总重量 / 总价值：");
disp([sum(w(selected)), sum(v(selected))]);

多阶段最短路（阶段明确的小网络）也可直接写贝尔曼更新：

% 阶段 1->2->3->4，节点按阶段划分
% cost{k}(i,j)：第 k 阶段从层内点 i 到下层点 j 的费用
INF = 1e12;
% 简单起见用完整邻接矩阵 dist，仅示意递推思想
dist = [
    0, 2, 5, INF;
    INF, 0, 3, 4;
    INF, INF, 0, 1;
    INF, INF, INF, 0
];
N = size(dist, 1);
V = INF(ones(1, N));
V(N) = 0;  % 终点
for u = N-1:-1:1
    for k = u+1:N
        V(u) = min(V(u), dist(u, k) + V(k));
    end
end
fprintf("从点1到点%d的最短路长度 = %g\n", N, V(1));

六、如何解释结果

完整的 DP 结果通常应报告：

状态定义与阶段划分（用一句话写清 $V(s)$ 的含义）；
转移方程与边界条件；
最优目标值；
回溯得到的决策序列（选哪些物品、走哪条路、各期产量等）；
复杂度：状态数、转移数、实际运行时间；
若做了离散化，说明网格步长及对最优值的影响；
与贪心、整数规划小实例对照，验证正确性。

解释时要把「表上的数字」翻译回业务：例如「第 3 期末库存为 5 时，未来最优成本是 12」比只给一个总最优值更有洞察力。

七、常见误区

1. 没有最优子结构却硬套 DP

若子问题最优拼接起来不是全局最优（例如某些带复杂耦合约束的游戏策略），贝尔曼方程不成立。

2. 状态遗漏关键信息

「无后效性」不满足时，表面能填表，答案却错。典型例子：状态只记位置不记剩余油量，而油量影响未来可达性。

3. 一维滚动时更新顺序错误

0-1 背包容量必须逆序；完全背包才顺序。顺序反了等于允许物品重复选取。

4. 把 DP 与「递归」混为一谈

递归若无记忆化会指数爆炸；DP 的关键是每个子问题只解一次并复用。

5. 忽略不可行与边界

终点、空容量、负下标、溢出容量未处理，会导致 Inf/NaN 传染或静默错误。

6. 状态空间过大仍强行枚举

维数灾难时，应改状态设计、用近似 DP、或转向 MILP / 启发式，而不是无脑加循环。

八、小结

动态规划的核心思想可以概括为：

把多阶段决策写成状态上的最优递推：每个状态的最优值，由更小子问题的最优值经一步决策转移得到，再回溯还原完整策略。

它适合具有清晰阶段结构与紧凑状态的精确优化问题，是背包、路径、库存、资源分配等题型的主力工具。

使用 DP 时，先花时间设计状态与转移，再写代码；务必用小规模枚举验证表值。状态爆炸或结构不符时，应及时换用数学规划或专用图算法，而不是把错误递推当作「近似算法」。

一、直观理解：把大决策拆成互相嵌套的小决策​

二、适用场景与优缺点​

三、核心原理：阶段、状态、决策与转移​

1. 阶段（Stage）​

2. 状态（State）​

3. 决策与转移（Decision & Transition）​

4. 计算顺序与回溯​

经典例子：0-1 背包​

四、关键决策：状态怎么设、表怎么填​

1. 状态是否充分又不过大​

2. 初始化与不可行标记​

3. 与最短路、整数规划的关系​

4. 何时不该用 DP​

五、MATLAB 示例​

六、如何解释结果​

七、常见误区​

1. 没有最优子结构却硬套 DP​

2. 状态遗漏关键信息​

3. 一维滚动时更新顺序错误​

4. 把 DP 与「递归」混为一谈​

5. 忽略不可行与边界​

6. 状态空间过大仍强行枚举​

八、小结​