企业官网建设流程全解析

这篇是动态规划系列里比较特殊的一篇，前几篇在解决同一个问题：怎么把一个实际问题翻译成状态和转移方程。现在翻篇了，递推式摆在眼前，接下来要回答的是一个更现实的问题——怎么在有限的内存、有限的时间、有限的数值精度里，把这个式子真正算出来。

我经常看到两种人卡在这一步。一种是刷题选手，状态方程写得头头是道，一上测评就WA，查了半天发现是INF设成了int最大值，溢出变成负数，或者dp数组初始化少写了一行；另一种是做工程的人，接手过和车辆动态规划相关的优化问题，模型、约束、目标都梳理清楚了，结果一估算复杂度发现状态规模大到根本无法运行。

这两种情况本质上同一个问题：动态规划模型负责描述问题的结构，数值求解算法负责把结构变成计算机能执行的具体步骤。这篇就把数值求解这一层拆开讲，包括状态怎么组织、边界怎么初始化、整数和浮点数各自有哪些坑、怎么估算复杂度、怎么用离散化和插值让连续问题也能进入DP框架。适合正在刷DP题单的竞赛选手，也适合想把DP用到路径规划、能量管理等工程场景的同学。

1. 从递推式到能跑的程序：状态空间的三种编排方式

1.1 记忆化搜索：哪里用到算哪里

先从最简单的斐波那契说起。F(n)=F(n-1)+F(n-2)是一个标准DP递推式，但第一次学递归的人几乎都写过暴力版本，复杂度2的n次方，n到40就开始卡。原因不是递推式错了，而是没有把算过的子问题缓存起来。记忆化搜索就是给递归加缓存：带着参数调用时先查表，有就直接返回，没有再往下算。

Python里现在一行就能搞定：

from functools import cache @cache def fib(n): if n < 2: return n return fib(n - 1) + fib(n - 2)

C++里一般手写一个memo数组，初始化为-1，遇到-1就继续递归。这套自顶向下的方式最大的好处是不需要显式设计计算顺序：递归天然保证在算dp(i)之前，依赖的dp(j)已经被算完。依赖关系复杂、状态稀疏的题目，用记忆化搜索会省很多心。

缺点是函数调用开销和递归深度。C++默认栈深度有限，状态深度到几十万层会直接爆栈；Python更不用说，递归层数默认一千多，很多状态多的题根本走不到底。所以现在很多选手默认选自底向上，不是因为它更高级，而是因为可控。

1.2 自底向上填表：把状态空间铺成一张能遍历的表

自底向上就是把dp[i]从依赖关系的最底层开始填。斐波那契无非是f[0]、f[1]先摆好，然后一个for循环从2到n：

for (int i = 2; i <= n; ++i) { f[i] = f[i - 1] + f[i - 2]; }

这张表非常规则，每个格子依赖前面的格子，所以循环顺序按下标从小到大就行。但一旦依赖关系乱掉，填表就不简单。最短路问题里如果转移图有环，就不能只填一遍，要像Bellman-Ford那样把所有边反复松弛n轮，直到数值不再变化。这里已经出现“数值迭代”的味道：有些DP不止填一遍，而是填到收敛，强化学习里的值迭代就是这样。

填表法的内存可以用滚动数组压缩。比如0/1背包，二维dp[i][w]只依赖i-1那一行，所以开两行滚动即可，空间从O(nW)降到O(W)。代价是必须小心覆盖顺序——0/1背包的容量循环要倒着走，因为正着走会让同一个物品被“重复选取”。这个坑属于典型的数值求解顺序错误，WA概率极高。

状态编排只是第一步。接下来这三个坑，几乎每个人都会踩：溢出、精度、非法状态。

2. 数值求解最容易翻车的地方：溢出、精度与非法状态

2.1 整数DP的溢出与INF选择

整数DP第一个经典翻车现场是溢出。斐波那契F(100)已经远超过int范围，n一上来就溢出成负数，后面的比较全废。所以只要规模允许，类型一律优先long long，不要等WA了再回头改。

第二个经典是INF怎么设。很多人求最小值时把dp数组全部初始化成一个大数，直接写INT_MAX。这看起来没毛病，实际上只要转移式里有加法，INT_MAX加上一个正数就会变成负数，非法状态反而成了最优解。竞赛圈里通用的做法是用0x3f3f3f3f：它约等于1.06e9，两个0x3f3f3f3f相加约2.12e9，仍然小于int的上限2.147e9。也就是说，哪怕你忘了判断非法状态，结果也不会因为溢出反转成负数，最多是一个很大的数，比较逻辑仍然成立。

这就是为什么memset(dp, 0x3f, sizeof(dp))会成为经典写法。它的值本身没有魔法，恰好卡在“够大且加不爆int”的区间里。

初始化成INF的另一层意义是让“无解”有明确的数值出口。递推完之后发现dp[n][w]还是INF，说明状态不可达，输出-1即可。如果初始化为0，非法状态被当成合法0参与比较，答案自然不可信。求最大值时同理，初始化为负INF，最稳妥是用long long的极小值，不要随手写0。

2.2 浮点DP的精度与判等

工程DP里的费用往往不是整数，比如油耗、时间、功耗，于是dp表变成double。这里有个更隐蔽的问题：状态值浮点化之后，比较大小是带误差的。比如两个方案理论值一样，一个算出来1.000000001，一个算出来0.999999999，用==比较就会漏掉真正的最优。

处理办法有两个方向。一是比较时用容差，fabs(a-b)小于某个eps就认为相等；二是在状态回溯阶段避免直接拿double去和dp表判等，而是在转移时就记录当前选的是哪个决策。记录决策数组是浮点DP的标准做法，能避免往回追溯时精度对不上。

还有一个工程常用的技巧是整数化：费用的单位从升改成毫升、从秒改成毫秒，把浮点费用乘一个足够大的系数后整体转成整数DP。整数没有精度误差，而且运算更快。代价是系数选太大可能溢出，所以选系数之前要先估算结果上界。

2.3 边界初始化：dp[0]到底等于多少

初始化没有统一答案，但有一个统一原则：dp的边界必须是真实存在的初始状态，而不是顺手写的0。

最长上升子序列里，每个元素自己可以单独成为一个子序列，所以dp[i]的初值是1，不是0；如果写0，答案整体小1，很多人WA在这行。最短路径DP里，起点dp[start]=0，其他点等于INF，松弛过程才能把真实距离传播出去。0/1背包里，容量0的dp值是0，其他容量取决于求最大还是最小，分别初始化为NEG_INF或INF。

判断初值是否正确的有效方法，是手推dp表的前两行：看第一次转移用的初值是否合理，结果是否符合直觉。这个五分钟的手动验证，通常比调一晚上调试器效率高得多。

3. 实战一：最长上升子序列从O(n^2)到O(nlogn)

3.1 O(n^2)递推写起来简单，算起来不简单

最长上升子序列是线性DP最标准的题目。定义dp[i]为以第i个数结尾的最长严格上升子序列长度，转移式是：

dp[i] = max(dp[i], dp[j] + 1) 其中 j < i 且 a[j] < a[i]

初值dp[i]=1，答案在所有dp[i]里取max。

这个递推式的数值计算量是Σ(i-1)，也就是n(n-1)/2。n=1000是50万次，秒过；n=1e4是5千万次，C++勉强能压线；n=1e5就是50亿次，任何普通实现都在超时边缘，Python基本没戏。

从数值求解的角度看，问题不在DP定义，而在转移里“扫描一遍所有j”这一步。要优化，得把这一步从O(n)变成O(logn)。

3.2 tail数组：状态压缩的典型示范

维护一个数组tail，tail[len]表示当前所有长度为len的严格上升子序列里，最小的末尾值是多少。遍历原数组时，对a[i]在tail中二分查找第一个大于等于a[i]的位置p：

• 如果找不到，说明a[i]能接到当前最长子序列后面，tail长度加1；
• 如果找到了，就更新tail[p]=a[i]。

最终答案就是tail的长度。

用一个具体序列手算一遍就清楚了。a = [4, 2, 3, 1, 5]：

• 读4，tail变为[4]；
• 读2，二分找到第一个大于等于2的位置，就是4，尾替换，tail变为[2]；
• 读3，找不到大于等于3的元素，扩展，tail变为[2, 3]；
• 读1，找到2，替换，tail变为[1, 3]；
• 读5，找不到，扩展，tail变为[1, 3, 5]。

答案就是3，对应子序列2, 3, 5或者1, 3, 5。

tail不是某一条具体的上升子序列，它维护的是“每个长度下的最小末尾值”，这个数组严格递增，所以能二分。严格说这版是贪心加二分，不是纯DP，但它的优化思路和DP里的状态设计高度同源。工程里常说的状态压缩不只是按位压，也可以是这种“把记录的内容从最大子序列值改成最小末尾值”的降维。做题时如果发现dp转移要扫全量历史，就可以想一下：能不能只保留对后续决策真正有影响的极值。

4. 实战二：车辆动态规划问题的数值求解

4.1 连续问题进入DP：时间离散化与状态网格化

之前几道的例子都是离散下标，很多人用DP处理连续变量时就会愣住。车辆动态规划问题典型就长这样：给定一条路线，要决定每一时刻发动机和电机的功率分配，让总油耗最低，同时把电池SOC控制在安全范围内。车速、功率、电量全是连续量，和“DP状态必须有限”的直觉完全冲突。

解法分两步。第一步时间离散，把路线切成固定间隔Δt的小段，比如1秒一段，3分钟就是180段；第二步把连续状态离散成网格，SOC从20%到80%按1%间隔取61个点。于是决策变成了分阶段决策问题：每一秒从候选功率表里选一档，系统状态沿着SOC网格移动。这就是把Bellman方程放进数值求解框架的过程。

SOC的变化量由电功率和时间决定，换算关系大概是：

deltaSOC(%) = P_mot * dt / (Q_batt * 3600) * 100

假设电池容量20kWh，1秒决策，电机功率-30kW，那么deltaSOC只有约0.04%。这个数字看起来很小，但对网格设计很关键，后面马上会说到。

4.2 逆向递推代码骨架：插值比四舍五入可靠

车辆能量管理的DP适合逆向递推，因为终点状态有约束。用J[t][s]表示从第t时刻SOC为s的状态出发、一直到终点的最小累计油耗。

// J[t][s]: 第t时刻SOC网格下标s，SOC = 20 + s * 1.0 const int N = 180; // 1秒一步，3分钟 const int M = 61; // SOC: 20% 到 80% const int K = 20; // 候选功率档数 const double INF = 1e18; vector<vector<double>> J(N + 1, vector<double>(M, INF)); // 终点惩罚：偏离目标SOC需要补回来 for (int s = 0; s < M; ++s) { double soc = 20.0 + s; J[N][s] = 0.5 * (soc - target_soc) * (soc - target_soc); } // 逆向递推 for (int t = N - 1; t >= 0; --t) { for (int s = 0; s < M; ++s) { double best = INF; for (int k = 0; k < K; ++k) { double delta = P_mot[k] * dt / (Q_batt * 3600.0) * 100.0; double soc_next = (20.0 + s) - delta; // 线性插值到网格 double pos = (soc_next - 20.0) / 1.0; int s_low = (int)floor(pos); int s_high = s_low + 1; s_low = max(0, min(M - 1, s_low)); s_high = max(0, min(M - 1, s_high)); double alpha = pos - s_low; double future = (1.0 - alpha) * J[t + 1][s_low] + alpha * J[t + 1][s_high]; double cost = fuel(P_req[k]) + future; best = min(best, cost); } J[t][s] = best; } }

很多实现图省事，用四舍五入找最近网格点。短时间内看不出问题，但结合刚才算的deltaSOC只有0.04%看就麻烦了：SOC每步变化不到1%网格的十分之一，round之后大部分时候状态原地踏步，隔好久才跳一格，中间的变化全被抹平。转移代价因此出现锯齿，最优功率档会在相邻决策之间跳来跳去。线性插值让转移代价是状态的连续函数，决策平稳很多。

填完整个J表之后，从J[0][起始SOC]出发，按每一步记录的最优决策回读功率档，就能还原出一条最优功率序列，SOC曲线、油耗曲线都能导出来分析。这套DP结果在工程里常作为离线基准，再配合实时控制器做在线修正，这就是车辆动态规划问题的一种标准数值求解用法。

4.3 网格密度、计算量和工程取舍

把刚才的例子量化一下：180段乘61个SOC点乘20个功率档，总共约22万次转移评价，普通电脑跑完不到0.1秒。如果把SOC步长从1%加密到0.1%，状态数变成801，计算量约293万；再把时间步长从1秒改成0.5秒，计算量翻倍到约586万。这些都在可接受范围内。

真正怕的是维度增加。如果把车速、坡度也同时离散成状态，状态变成四维，哪怕每个维度只有几十个点，状态总数也可能到百万甚至千万级，转移再乘一个几十，就直奔上亿次。所以工程落地第一条原则是：能用物理关系消掉的变量一定要消掉。功率需求已知时，发动机功率和电机功率不是两个自由变量，二者之和固定，决策维度直接降一维。

另外要明确：DP数值求解擅长离线全局最优，模型不匹配和外部扰动是另一回事。车辆问题里，离线算出来的策略在线使用时还要考虑实时修正，常见做法是用DP结果做基准，再用带约束的局部优化器做小范围调整。

5. 效率边界：动手写代码前先算三笔账

5.1 复杂度可行性：状态数乘以转移数

写任何DP之前，先把状态规模乘一遍。以C++为例，2GHz左右的CPU，大致体感如下：

用Python的话，这个门槛大约还要再降两个数量级。这个表不是精确科学，就是让你对“下一步要不要优化”有感觉。看完表才谈得上选算法：n=1e4的O(n^2)可以接受，n=1e5必须上O(nlogn)；集合类状态n一旦超过20就要警惕，因为2的20次方约1e6还能接受，2的30次方约10亿直接内存爆炸。

5.2 滚动数组与循环顺序：数值覆盖的经典陷阱

滚动数组下，0/1背包容量循环必须从大到小走，完全背包从小到大走。同一条转移式，只改循环方向就能得到两种意义完全不同的结果。原因一句话：倒序保证本轮更新dp[w]用的dp[w-w_i]来自上一轮，正序会让它来自本轮，等于允许同一个物品被反复选择。

这个覆盖顺序问题在所有带滚动数组的DP里都会出现。改代码之前先在纸上画一遍依赖线：新格子依赖旧格子的哪个位置，这个位置会不会在旧值被用掉之前就被覆盖。

至于记忆化搜索和填表的选择，我的习惯是：状态稀疏、依赖关系乱、带剪枝的，优先记忆化；状态规则密集的，优先填表；内存敏感的，用滚动数组；集合子集类问题，用二进制状态压缩。大部分DP题的代码量差异，都来自于这个选型。

5.3 提交前自查：三个数值问题

养成了提交前自查习惯之后，WA率会显著下降。我一般只问三个问题：

第一，边界对吗？dp[0]是否真的对应合法初始状态？初值是0、1还是INF，和第一次转移是否自洽。

第二，依赖算了吗？填表顺序能否保证转移用的dp值已经算过？滚动数组有没有覆盖掉上一轮需要的数据？

第三，数值安全吗？量级会不会溢出？INF加正数会不会变成负数？double比较有没有用容差？

再加一个问题：无解有出口吗？dp的终值如果还是INF，程序知道要输出-1吗？

刷DP题单时这三个问题会反复出现，LIS的二分优化、车辆DP的插值、背包的滚动顺序，最后都能归到这三条上。

最后说一点个人经验。很多文章讲DP会把重点放在状态设计和转移方程上，这当然没错，但真正让一个DP可运行的，往往是那些数值细节：INF怎么设、初始化怎么填、循环顺序怎么排、用float还是double、离散网格怎么取。我之前做车辆能量管理的策略优化时，前三次仿真结果都很离谱，最后发现是SOC转移时用了round，把离散误差放大了，改成线性插值之后曲线立刻合理。刷题时也常因为没判断非法状态导致答案偏离。现在我的习惯是：拿到DP题先写边界，再写转移，最后手动跑一遍dp表前两行确认数值轨迹，然后再提交。这个小习惯，值回票价。