第四章：鬼谷出山，动态规划
一眼春秋，望穿风云。
第四章：鬼谷出山，动态规划
第一幕：鬼谷子出山，魏国请圣
魏国，大梁城，云梦算法阁。
阁高九层，飞檐斗拱，最顶层终年云雾缭绕，寻常人不得入。传闻此阁中住着一位算法圣人——鬼谷子，已闭关三十年，参悟《鬼谷算法》最后一重。
今日，云梦阁前，魏惠王亲率百官跪候。
“求鬼谷圣人出山，救魏国于危难！”
魏惠王三拜九叩，身后庞涓伏地不起，额头抵着青石，血迹斑斑。
“弟子无能，败于齐国王子姬玄，损魏国威名，请师尊责罚！”
良久，阁顶云雾散开一道缝隙，传来苍老声音：
“姬玄…得《九章算法》第一卷，破你三阵？”
“是。” “用何法破你‘最小割’阵？” “他…他临时增设虚节点，绕过最小割。”
阁顶沉默片刻，忽有笑声：“倒是个聪明孩子。进来。”
庞涓大喜，连滚爬入阁中。
顶层无桌无椅，只有满地算法符文流动如河。中央蒲团上，坐着一位麻衣老者，须发皆白，但双目清澈如婴童——正是鬼谷子。
“你败得不冤。”鬼谷子缓缓道，“你学的是‘死算法’，他用的却是‘活思维’。”
“求师尊指点！” “算法之道，分三重境界。”鬼谷子伸出一指，“第一重：记算法，知其然；第二重：懂原理，知其所以然；第三重：无算法，万物皆可为算法。”
他看向西方，目光似穿透千里：“这个姬玄…已摸到第三重门槛。”
庞涓骇然：“他才多大？！” “天赋，与年纪无关。”鬼谷子起身，“也罢，老夫闭关三十载，也该活动活动筋骨了。”
他袖袍一挥，地面符文汇聚成一张中原地图。
“齐伐魏，必走两条路：一为西线经桂陵，二为北线过马陵。”鬼谷子指点地图，“你可知，姬玄会走哪条？”
庞涓沉吟：“按常理，应走桂陵，地势平缓，粮草易运。” “所以他不走桂陵。”鬼谷子微笑，“他会走马陵。”
“为何？马陵道险，易中埋伏！” “正因易中埋伏，才要走。”鬼谷子眼中闪过精光，“他已猜到我会在桂陵布阵，故而反其道行之。此子…善用‘逆向思维’。”
庞涓恍然：“那我们在马陵设伏？” “不。”鬼谷子摇头，“我们在两条路都设伏。”
他指尖在地图上划出复杂路径：“此乃‘动态规划伏击网’——无论他走哪条路，我们都能以最优兵力调度应对。”
第二幕：齐国点兵，背包难题
齐国，临淄，校场。
十万大军列阵，旌旗蔽日。姬玄一身银甲，腰悬玉笔，立于点将台上。身旁芈月白衣胜雪，手持楚国“凤鸣算盘”。
田忌呈上军册：“殿下，粮草已备：粟米三十万石，草料二十万车，箭矢一百万支…但运输车辆有限，只能载重八万石。”
姬玄皱眉：“十万大军，日耗粟米五千石，三十万石仅够六十日。若战事拖延…”
“还有更大问题。”后勤官苦脸，“车辆还要运箭矢、帐篷、药材…如何分配载重，才能最大化战力？”
这分明是经典的背包问题（Knapsack Problem）！
物品：粮草、箭矢、帐篷、药材… 重量：各不相同 价值：对战斗力的贡献度不同 背包容量：车辆总载重八万石
需选择物品组合，使总价值最大。
台下将领议论纷纷： “当然先运粮草！没饭吃打什么仗？” “箭矢重要！守城进攻都要用！” “帐篷呢？将士露宿生病怎办？”
姬玄抬手，全场静下。
“此乃‘多维背包问题’，”他朗声道，“不是简单取舍，而要动态规划优化。”
他在空中画出表格：
定义 dp[i][w]：前i种物品，总重量不超过w时的最大价值
状态转移：
dp[i][w] = max(
dp[i-1][w], // 不选第i种
dp[i-1][w-weight[i]] + value[i] // 选第i种
)
但现实更复杂——物品分类别：粮草是消耗品，随时间减少价值；箭矢可回收部分；帐篷多人共用…
芈月轻声道：“可用‘分组背包’思路，每类物品内选最优组合，再类间优化。”
姬玄点头，二人联手推演。
半炷香后，方案出炉：
最优分配：
1. 粮草：五万石（保障百日）
2. 箭矢：两万石（三十万支，可回收）
3. 帐篷：五千石（轻便型，五人一帐）
4. 药材：五千石（精简品种）
5. 机动：预留一万石载重，沿途补给
众将叹服。
但姬玄心中仍有隐忧——这个最优解，是基于已知信息。若魏国破坏粮道，或天气突变…价值函数就会变化。
需要动态调整的算法。
“田将军，”姬玄下令，“分三批运输，每批路线不同，且每批都含各类物资。如此，即使一路被劫，另两路也能支撑。”
这是分布式背包的思路。
田忌领命而去。
第三幕：马陵道上，最长公共子序列
三日后，大军开拔。
姬玄果然选择了马陵道——山路崎岖，但可直插魏国腹地。
行军第三日，先锋截获魏国密探，搜出一份加密军情。
密文是两串数字：
序列A：3 1 4 1 5 9 2 6 5 3
序列B：3 4 5 9 2 6 5 3 8 9
芈月细看：“这是…圆周率π和自然常数e的数字序列？但被打乱了。” “不，”姬玄凝神，“这是**最长公共子序列（LCS）**的载体。”
他想起前世见过的情报加密法：将真实信息藏在两个序列的公共子序列中。
“破译需要找到A和B的最长公共子序列…”姬玄在地上推算，“动态规划经典问题。”
构建二维表dp[i][j]，表示A前i个字符和B前j个字符的LCS长度。
转移方程：
if A[i] == B[j]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
芈月同步心算，两人配合，很快算出LCS：
3 4 5 9 2 6 5 3
“这是数字序列，对应什么？”田忌疑惑。
姬玄看向芈月：“楚国有种‘数字密码本’，每数字对应一字…”
芈月从怀中取出一卷帛书——正是楚国军用密码本。
对照翻译：
3 4 5 9 2 6 5 3
桂 陵 有 伏 勿 入 转 向
“桂陵有伏！”田忌大惊，“我们走的是马陵，那…”
姬玄脸色一变：“不好！这是误导！魏国知道我们能破译，故意让我们以为桂陵有伏，实则伏兵在…”
话音未落！
“轰——！”
两侧山崖滚石如雨！
“埋伏！是马陵！”田忌大吼，“结阵！”
但为时已晚，魏军如蚁群涌出，领头之人——正是庞涓！
“姬玄！今日就是你的死期！”
第四幕：多维背包杀阵
庞涓立于山巅，身后站着八名黑袍阵师，各持算筹，布下的是改良版背包杀阵！
阵法显形：空中浮现无数光球，每个光球代表一种“攻击资源”——箭雨、滚石、毒雾、地刺…
每个光球有重量（消耗灵力）和价值（杀伤力）。
阵法规则：庞涓每轮有固定“灵力容量”，需选择光球组合，最大化杀伤力。
这正是动态规划背包问题，但庞涓将其化为杀阵！
“姬玄，”庞涓狞笑，“你不是善解背包问题吗？那就解解这个实时动态背包！”
第一轮，庞涓选择：箭雨（重3，伤5）+滚石（重5，伤8）=总伤13
箭石齐发！齐军死伤数百。
姬玄急令：“举盾！分散！”
他同时大脑飞转：要破此阵，必须预测庞涓下一轮选择，提前防御。
但庞涓不是死算法——他会根据齐军阵型调整价值判断。
“这是对抗性动态规划…”姬玄额头见汗，“我需要建立庞涓的决策模型…”
芈月喊道：“用博弈树！假设庞涓是理性人，每轮选当前最优…”
“不，”姬玄摇头，“庞涓背后有鬼谷子，决策可能更深远——会为后续轮次牺牲当前收益。”
这是带时间折扣的背包问题！
姬玄闭目，全力计算：
设总轮数T=10，每轮容量C=10 光球种类K=8，每轮价值可能变化 庞涓目标：最大化 Σ β^t * V_t （β为折扣因子）
需要逆向推导：从最后一轮开始，往前计算最优策略。
“给我三息！”姬玄玉笔狂舞。
芈月则率亲卫结阵死守。
三息后，姬玄睁眼：“下一轮，他会选毒雾（重4，伤6）+地刺（重6，伤9）！因为下一轮箭雨价值会下降！”
“防毒！垫厚革！”
果然，第二轮庞涓选了毒雾+地刺。
但齐军已提前防护，伤亡大减。
庞涓脸色一沉：“你能预测一轮，能预测十轮吗？”
他改变策略——开始随机化选择！用一定概率混合不同组合，让姬玄无法确定预测。
“这是随机化动态规划…”姬玄压力骤增，“需要计算混合策略的期望值…”
计算量暴涨！
就在这时——
“姬玄，看这个。”
芈月递来一枚玉佩，上面有楚国秘传算法：“蒙特卡洛树搜索（MCTS），可近似解大规模随机动态规划！”
姬玄大喜，立即应用：
- 选择：从根节点（当前状态）开始，用UCB公式选子节点
- 扩展：扩展新节点（庞涓的可能选择）
- 模拟：随机模拟后续轮次
- 回溯：更新节点统计量
虽不精确，但足够指导防御！
两人联手，姬玄计算主干，芈月并行模拟，硬是在庞涓的随机攻击中，护住主力。
十轮过后，齐军伤亡三千，但未溃散。
庞涓灵力将尽，咬牙道：“师尊说得对…你果然难缠。但接下来…是真正的杀招！”
他捏碎一枚玉符。
天地变色！
第五幕：鬼谷真身，状态压缩DP
云层破开，一道麻衣身影缓缓降落。
鬼谷子真身降临！
他并未看庞涓，直接看向姬玄：“小娃娃，能破我徒弟十轮攻击，算你有些本事。”
姬玄持笔行礼：“晚辈姬玄，见过鬼谷前辈。” “不必客气。”鬼谷子微笑，“老夫此来，是为杀你。”
他说得轻描淡写，却让所有人脊背发寒。
鬼谷子袖袍一挥，地面升起八十一盏铜灯，每灯有明暗两种状态。
“此阵名‘状态压缩DP杀局’。”鬼谷子道，“八十一盏灯，代表八十一个变量，每灯状态0或1，总状态数2^81——你穷举不了。”
姬玄凝神：“前辈要晚辈解何题？” “很简单，”鬼谷子指向灯阵，“找出一种明暗模式，使得相邻三灯中，至少两灯明，且总明灯数最多。”
这是约束优化问题，但规模太大。
“给你三炷香，”鬼谷子坐下，“解出，我退兵；解不出，十万齐军…尽葬于此。”
田忌怒吼：“鬼谷子！你以大欺小！” “战争，本就不公平。”鬼谷子闭目。
姬玄盯着灯阵。
2^81 ≈ 2.4e24，天文数字，穷举不可能。
必须用状态压缩动态规划（状压DP）！
将每行灯的状态压缩为一个二进制数，行间转移时检查约束。
但八十一盏，若是9×9方阵，每行9盏，状态数2^9=512，可行！
“前辈，”姬玄忽然道，“这八十一盏灯，是9行9列，对吗？” 鬼谷子睁眼，闪过一丝讶异：“你如何知道？” “因为81=9²，且您布阵时，暗中按九宫方位。”姬玄道，“所以，这是二维状压DP。”
他快速建模：
设dp[i][mask]：处理到第i行，当前行状态为mask时的最大明灯数。
转移需满足：
- 行内约束：mask自身不能有连续三暗
- 行间约束：mask与上一行mask_prev，任意列上两行不能都暗（至少一明）
“但还有‘相邻三灯’约束…”芈月提醒，“是三维相邻：上下左右？” “应是包括对角。”姬玄推演，“那就是三维邻域约束，需同时检查当前行、上一行、上上行…”
复杂度激增！
但姬玄发现一个关键：约束本质是局部检查，可预处理所有合法状态。
他分三步：
- 预处理所有合法行状态（512中筛选）
- 预处理行间合法转移对
- 动态规划计算最优
半炷香后，姬玄开始解。
一炷香时，他已推演到第五行。
两炷香时，抵达第九行。
最后一炷香燃尽前——
“找到了！”姬玄玉笔一点，八十一盏灯按特定顺序明灭！
最优解：五十三盏明灯！
鬼谷子凝视灯阵良久，忽然大笑：
“好！好！好！”
他连说三个好字，起身：“三十年未见如此天赋。姬玄，你过关了。”
庞涓急道：“师尊！不能放他走！” “闭嘴。”鬼谷子冷声道，“算法之道，言出必践。我说过解出就退兵。”
他看向姬玄：“不过…这只是开始。下一阵，在魏都大梁等你。”
说罢，袖袍一卷，带庞涓及魏军消失。
第六幕：军情突变，秦国背刺
马陵伏击虽退，但齐军伤亡不小，休整三日。
期间姬玄收到两份急报：
第一份来自临淄：齐王身体反复，递归毒似有余孽未清。
第二份更致命——秦国出兵了！
秦军十万，由太子嬴驷统领，以“调解齐魏争端”为名，兵分两路： 一路直扑齐国西境； 一路绕道赵国，意图断齐军归路！
“嬴驷…”姬玄握紧军报，“他在迷宫败于我手，这是报复。”
田忌焦急：“殿下，我们前有魏国，后有秦国，若赵国也被秦拉拢…三面受敌！”
芈月却道：“未必。我楚国有密报，赵王不愿掺和，但秦以‘算法共享’为诱，赵国有些动摇。”
“算法共享？”姬玄皱眉。 “秦国声称，若列国共抗齐，愿公开《秦法算经》前三卷。”
姬玄冷笑：“嬴驷倒是舍得。但我们也有筹码——《九章算法》第一卷，我已公开基础篇。”
“不够，”芈月摇头，“各国要的是进阶算法，特别是…军阵算法。”
姬玄沉思良久，忽然问：“公主，楚王那里…” “我已传信父王，”芈月轻声道，“楚国可出兵五万，从南线牵制秦国。但…父王有条件。”
“什么条件？” “一、你需亲自赴郢都，解楚王三道算法难题；二、…”芈月脸微红，“公开我们的婚约。”
姬玄一愣。
田忌等将领却大喜：“殿下！此乃良机！得楚国相助，可破秦魏之围！”
但姬玄知道没那么简单——楚王的三道难题，必是生死考验。
“我去。”姬玄决然道，“但大军不能停，继续伐魏。田将军，你率主力佯攻大梁，拖住魏军。我轻骑赴楚，最快半月回。”
“殿下不可！”田忌反对，“您是主帅，怎能离军？且途中危险…”
“正因危险，才要快。”姬玄看向芈月，“公主，你随我回楚吗？” 芈月点头：“我带路，有楚国秘道，可缩短路程。”
计划定下：姬玄、芈月带百名亲卫赴楚；田忌率军继续进逼大梁。
但就在当夜，异变再生。
第七幕：递归咒爆发，芈月舍身
子时，姬玄正在推演赴楚路线，忽听隔壁芈月帐中传来痛呼！
冲入帐内，只见芈月倒在地上，胸前浮现黑色递归纹路——竟与齐王所中类似！
“月儿！”姬玄扶起她。 芈月脸色惨白：“是…是邹忌…他临死前，在我身上下了递归咒…现在发作了…”
姬玄神识探查，果然发现芈月经脉中有递归代码，但比齐王的更隐蔽、更恶毒！
“此咒触发条件…”姬玄脸色大变，“是情绪波动！你对我动情越深，递归越深！”
这是情感绑定递归咒，专门针对相爱之人！
芈月苦笑：“邹忌…好狠…他知道你会救我父王，所以在我身上下咒…你若救我，会耗尽全力；若不救…你会内疚一生。”
姬玄红眼：“我一定会救你！”
但探查后发现，此咒与芈月心脉绑定，强行破解会伤她性命。
只能在递归中解——进入递归幻境，找到终止条件。
“田将军！”姬玄下令，“全军警戒，我要为公主驱咒，不得打扰！”
“殿下，大战在即，您若消耗过度…” “执行命令！”
姬玄扶芈月盘坐，两人四掌相对，神识进入递归幻境。
幻境中，是无尽递归迷宫。
每个转角都出现芈月的记忆片段： 幼年学算法、楚国宫廷争斗、第一次见姬玄、迷宫并肩、马陵共战…
每个片段都是递归调用，一层套一层。
姬玄在迷宫中疾走，寻找递归出口。
他很快发现规律：每个记忆片段都有个“情感值”，正情感加深递归，负情感则减弱。
“所以…要让她回忆痛苦之事？”姬玄犹豫，“但那会伤她…”
正迟疑时，幻境深处传来芈月的声音：
“姬玄…不要顾忌…破咒要紧…”
姬玄咬牙，开始引导芈月回忆：
- 母亲早逝的痛苦
- 兄弟争权的残酷
- 作为公主的束缚
- …
递归深度果然减缓。
但芈月气息也越来越弱——以痛苦压制递归，如同饮鸩止渴。
“不对！”姬玄猛然醒悟，“邹忌的陷阱就在于此！若我继续引导痛苦，月儿心神会崩溃！”
必须另寻他法。
“递归咒…本质是算法。”姬玄冷静下来，“只要是算法，就有逻辑，就可破解。”
他仔细分析递归结构，发现一个隐藏规律：
每次递归调用，情感值都会乘以一个系数β（0.9）
这意味着，递归深度越深，情感影响越小，但总有一个极限值。
“这是几何级数递归！”姬玄眼睛一亮，“总和有极限：S = a/(1-β)！”
只要算出初始情感值a，就能知道总递归深度！
他开始在幻境中收集数据，计算a值。
一炷香… 两炷香…
“算出来了！”姬玄在迷宫中心找到递归基座——一枚黑色符文。
他玉笔一点，注入计算出的极限值：
“以情为始，以数为终——破！”
符文炸裂，递归幻境崩塌。
现实世界，两人同时吐血。
但芈月胸前黑纹，开始消退。
“成功了…”姬玄虚弱道。
芈月缓缓睁眼，泪光闪烁：“你…你又救我一次…”
“因为…”姬玄微笑，“你值得。”
两人相拥，帐外月光如水。
第八幕：楚国之行，三道难题
五日后，楚国郢都。
楚王宫，算法殿。
楚王熊商高坐王位，左右分立楚国算法宗师。芈月站于殿中，姬玄跪拜行礼。
“齐王子姬玄，”楚王声音威严，“月儿传信，说你算法通神，且与她两情相悦。但本王不能凭一面之词将公主许你，更不能轻易出兵助齐。”
他竖起三根手指：“三道题。解出，楚齐联姻，楚军助齐；解不出…你自行离去，月儿永留楚国。”
“晚辈愿试。” “第一题，”楚王挥手，“楚粮调度。”
场景浮现：楚国七大粮仓，需调粮至三处边关，每仓储量、每关需求、道路运力皆不同，且部分道路有盗匪（损耗）。
“要求：最小化总损耗，且保证边关粮草不缺。”
这是最小费用最大流问题！
姬玄快速建模： 源点：七粮仓（供应量） 汇点：三边关（需求量） 中间：转运节点 边：道路（容量、单位损耗）
算法：在最大流基础上，找费用最小的增广路径。
他用连续最短增广路算法（SSA）——每次用Bellman-Ford找最小费用路径，增广，直至满足需求。
半炷香，解出最优方案。
楚王点头：“第二题——楚宫侍卫排班。”
宫廷侍卫三百人，需排一月班次，约束极多：
- 每人每周休二日
- 每日每班需特定人数
- 老手新手需搭配
- 某些人不能同班（有仇）
- 某些人必须同班（搭档）
- 最大化侍卫满意度
这是约束满足问题（CSP）+ 优化，规模巨大。
但姬玄看出本质：可转化为整数规划，用分支定界法求解。
他构建数学模型： 变量：x[i,d,s] = 1表示侍卫i在第d日值s班次 约束：线性等式/不等式 目标：最大化 Σ 满意度权重
然后分支定界搜索解空间。
这次用了一炷香，给出接近最优解。
楚王眼中已有赞许：“第三题…是月儿母亲留下的。”
他取出一卷竹简：“楚国千古难题——汉诺塔最少步数证明。”
汉诺塔问题：三根柱子，N个盘子从A移到C，每次只能移一个，且大盘不能在小盘上。
已知最少步数H(N) = 2^N - 1，但需要数学归纳法证明。
这不是算法题，是数学证明题。
姬玄接过竹简，沉思片刻，开始书写：
证明：
1. 基础：N=1时，H(1)=1=2^1-1，成立。
2. 归纳假设：假设对N=k成立，即H(k)=2^k-1。
3. 对N=k+1：
- 将前k个盘从A移到B（用C辅助），需H(k)步
- 将第k+1个盘从A移到C，需1步
- 将B上的k个盘移到C（用A辅助），需H(k)步
- 总步数：H(k+1) = 2*H(k) + 1
= 2*(2^k - 1) + 1
= 2^(k+1) - 2 + 1
= 2^(k+1) - 1
4. 由归纳法，对所有N成立。
写罢，呈上。
楚王看完，长叹一声：“月儿母亲当年，就是想证此题而心力耗尽…你竟如此轻松。”
他起身，走下王位，扶起姬玄：
“本王准了。楚齐联姻，三月后大婚。楚国出兵五万，助齐抗秦！”
殿内欢呼。
芈月泪流满面，与姬玄相视而笑。
尾声：三军合围，最终决战
三月后，楚齐联军大破秦军于河西，嬴驷重伤逃回秦国。
魏国大梁被围，鬼谷子亲自守城，布下最终杀阵——“NP完全杀局”，号称无人可破。
但姬玄得楚国助力，又公开《九章算法》部分进阶篇，引来列国算法高手助阵。
最终决战前夜，姬玄与芈月在帐中。
“明日破阵，你有多少把握？”芈月问。 “五成。”姬玄诚实道，“鬼谷子的NP完全阵，本质是旅行商问题（TSP）的变种，要找哈密顿回路…那是NP-hard，没有多项式解法。”
“那如何破？” “用近似算法，”姬玄眼中闪过精光，“找不到最优解，就找足够好的解。战争…本就是妥协的艺术。”
他握住芈月的手：“而且，这次有你在。”
芈月靠在他肩上：“等战争结束…” “等结束，”姬玄轻声道，“我带你游遍中原，看尽算法奇观。”
帐外，星垂平野，大战将临。
而姬玄不知道的是…
鬼谷子站在大梁城头，遥望齐营，手中捏着一枚血色玉简。
玉简上浮现一行小字：
“姬玄，你以为赢了？真正的敌人…来自算法之外。”
“系统本身，即将觉醒。”
【下章预告】 第五章：系统觉醒，时空乱流
核心算法：P vs NP 终极之谜、近似算法极限、随机算法概率分析
关键冲突：天机系统突然具现化，要回收所有算法知识
感情考验：芈月被系统标记为“异常数据”，面临抹杀
最终抉择：姬玄必须在拯救爱人和保存算法文明间选择…
【本章算法知识点】
- 背包问题：0/1背包、多维约束、随机化版本
- 最长公共子序列：动态规划经典，应用于密码破译
- 状态压缩DP：用二进制表示状态，处理大规模组合问题
- 最小费用最大流：SSA算法，Bellman-Ford找增广路
- 约束满足与整数规划：分支定界法
- 汉诺塔与数学归纳法：经典递归问题的数学证明
- NP完全问题：旅行商问题（TSP）与近似算法
（对应LeetCode：416分割等和子集、1143最长公共子序列、134加油站、473火柴拼正方形等…）
