• 第四章-鬼谷出山，动态规划

• ◀ 返回

第五章：系统觉醒，时空乱流

第一幕：NP完全杀局，近似破阵

大梁城下，十万联军列阵。

城头鬼谷子麻衣飘飘，脚下是绵延十里的算法符文——正是“NP完全杀阵”。阵法光芒流转，隐约可见无数节点与路径交织，正是旅行商问题（TSP）的具现化。

“姬玄，”鬼谷子声音传遍战场，“此阵需从起点遍历所有节点一次且仅一次，最后回起点，求最短路径。但节点数…一万。”

一万节点的TSP！解空间规模是(n-1)!/2，远超宇宙原子总数。

庞涓在旁狞笑：“师尊此阵，穷尽天下算法亦不可破！姬玄，今日就是你葬身之地！”

齐楚联军将领皆面色惨白。

芈月紧握姬玄的手：“真无解吗？”

“有近似解。”姬玄凝神观察，“TSP虽NP-hard，但有好近似算法。看此阵结构…节点分布有规律，并非最坏情况。”

他大脑飞转，分析阵法特征：

1. 满足三角不等式？观察节点间距，似乎满足——从i到j的直接距离 ≤ 从i经k到j的距离。若是，则可用Christofides算法达到1.5倍近似比。

2. 欧几里得TSP？节点在平面上，距离为直线——若是，则有多项式时间近似方案（PTAS）。

姬玄凌空而起，神识扫描整个大阵。

片刻，他落地：“此阵是度量TSP，满足三角不等式。可用Christofides算法！”

Christofides算法步骤：

1. 构建最小生成树（MST）
2. 在奇度节点间找最小完美匹配
3. 将MST与匹配合并成欧拉回路
4. 短路法转为哈密顿回路

姬玄对田忌下令：“分四队，每队负责一个阶段！楚军负责构建最小生成树，齐军负责寻找匹配…”

大军如臂使指，开始“计算”。

第一阶段：构建最小生成树。楚军用Prim算法——从任意节点开始，不断添加最短边，避免成环。

第二阶段：找奇度节点最小完美匹配。齐军用**开花算法（Blossom Algorithm）**处理一般图匹配。

阵法开始震动！

鬼谷子脸色微变：“他竟然知道Christofides…但一万节点的匹配计算，你们时间不够！”

确实，开花算法虽多项式时间，但O(n³)，一万节点需要太久。

“改用贪婪近似！”姬玄当机立断，“对奇度节点按距离排序，贪婪配对——虽不是最优匹配，但仍在2倍范围内。”

这牺牲精度换时间。

两炷香后，MST和匹配完成，合并成欧拉回路。

最后一步：短路法。遍历欧拉回路，跳过已访问节点，得到哈密顿回路。

“成了！”姬玄一剑指向阵法核心，“破！”

大军沿计算出的路径冲锋，阵法光芒剧烈闪烁，最终——

“轰隆！”

NP完全杀阵，破！

庞涓目瞪口呆：“怎么可能…” 鬼谷子却笑了：“好一个近似算法。姬玄，你已摸到算法之道的真谛——世间本无完美解，唯有足够好。”

他袖袍一挥：“魏军…投降。”

第二幕：系统异常，数据风暴

魏国投降，列国震动。

姬玄携芈月凯旋归齐，齐王大宴三日，宣布三月后为二人举行大婚。

但就在庆功宴当夜，异变突生。

子时，姬玄在房中查看系统界面，准备兑换新婚礼物。忽然——

【警告！检测到异常数据流】 【来源：系统核心层】 【内容：时空参数错乱，因果链断裂风险】

几乎同时，窗外天空出现奇景：星辰位置错乱，月亮一分为三，时空如水面般泛起涟漪。

“这是…”姬玄冲到院中。

芈月也惊醒出来，看到天空异象，脸色煞白：“我听师尊说过…这是‘算法天道’崩溃的前兆…”

“算法天道？” “就是维持这个世界的底层规则。”芈月颤声道，“若天道崩溃，万物将归为混沌…”

话音未落，姬玄脑中系统疯狂报警：

【紧急！系统被未知存在入侵！】

【入侵者身份：？？？】

【目标：回收所有超时代算法知识】

【警告：宿主可能被标记为“异常数据”】

突然，一道白光从天空射下，笼罩姬玄！

“姬玄！”芈月想冲过去，却被无形屏障弹开。

白光中，响起冰冷的机械音：

“检测到异常数据：姬玄” “携带超时代算法知识：动态规划、图论、NP理论…” “来源：非法时空穿越” “处理方案：数据回收，宿主抹杀”

姬玄感到灵魂在被剥离，算法知识如潮水般被抽走！

• 第三章-图论杀局，临淄风云 ◀ 返回

第四章：鬼谷出山，动态规划

第一幕：鬼谷子出山，魏国请圣

魏国，大梁城，云梦算法阁。

阁高九层，飞檐斗拱，最顶层终年云雾缭绕，寻常人不得入。传闻此阁中住着一位算法圣人——鬼谷子，已闭关三十年，参悟《鬼谷算法》最后一重。

今日，云梦阁前，魏惠王亲率百官跪候。

“求鬼谷圣人出山，救魏国于危难！”

魏惠王三拜九叩，身后庞涓伏地不起，额头抵着青石，血迹斑斑。

“弟子无能，败于齐国王子姬玄，损魏国威名，请师尊责罚！”

良久，阁顶云雾散开一道缝隙，传来苍老声音：

“姬玄…得《九章算法》第一卷，破你三阵？”

“是。” “用何法破你‘最小割’阵？” “他…他临时增设虚节点，绕过最小割。”

阁顶沉默片刻，忽有笑声：“倒是个聪明孩子。进来。”

庞涓大喜，连滚爬入阁中。

顶层无桌无椅，只有满地算法符文流动如河。中央蒲团上，坐着一位麻衣老者，须发皆白，但双目清澈如婴童——正是鬼谷子。

“你败得不冤。”鬼谷子缓缓道，“你学的是‘死算法’，他用的却是‘活思维’。”

“求师尊指点！” “算法之道，分三重境界。”鬼谷子伸出一指，“第一重：记算法，知其然；第二重：懂原理，知其所以然；第三重：无算法，万物皆可为算法。”

他看向西方，目光似穿透千里：“这个姬玄…已摸到第三重门槛。”

庞涓骇然：“他才多大？！” “天赋，与年纪无关。”鬼谷子起身，“也罢，老夫闭关三十载，也该活动活动筋骨了。”

他袖袍一挥，地面符文汇聚成一张中原地图。

“齐伐魏，必走两条路：一为西线经桂陵，二为北线过马陵。”鬼谷子指点地图，“你可知，姬玄会走哪条？”

庞涓沉吟：“按常理，应走桂陵，地势平缓，粮草易运。” “所以他不走桂陵。”鬼谷子微笑，“他会走马陵。”

“为何？马陵道险，易中埋伏！” “正因易中埋伏，才要走。”鬼谷子眼中闪过精光，“他已猜到我会在桂陵布阵，故而反其道行之。此子…善用‘逆向思维’。”

庞涓恍然：“那我们在马陵设伏？” “不。”鬼谷子摇头，“我们在两条路都设伏。”

他指尖在地图上划出复杂路径：“此乃‘动态规划伏击网’——无论他走哪条路，我们都能以最优兵力调度应对。”

第二幕：齐国点兵，背包难题

齐国，临淄，校场。

十万大军列阵，旌旗蔽日。姬玄一身银甲，腰悬玉笔，立于点将台上。身旁芈月白衣胜雪，手持楚国“凤鸣算盘”。

田忌呈上军册：“殿下，粮草已备：粟米三十万石，草料二十万车，箭矢一百万支…但运输车辆有限，只能载重八万石。”

姬玄皱眉：“十万大军，日耗粟米五千石，三十万石仅够六十日。若战事拖延…”

“还有更大问题。”后勤官苦脸，“车辆还要运箭矢、帐篷、药材…如何分配载重，才能最大化战力？”

这分明是经典的背包问题（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种
)

但现实更复杂——物品分类别：粮草是消耗品，随时间减少价值；箭矢可回收部分；帐篷多人共用…

芈月轻声道：“可用‘分组背包’思路，每类物品内选最优组合，再类间优化。”

姬玄点头，二人联手推演。

• 第二章-九章迷宫，群雄逐鹿

• ◀ 返回

第三章：图论杀局，临淄风云

第一幕：急报惊变，算法反噬

暮色如血，马车在官道上飞驰，车轮碾起滚滚烟尘。

车内，姬玄握着临淄急报的手微微颤抖。竹简上只有八个字，却字字惊心：

“王遭反噬，危，速归，忌”

“田忌将军的笔迹，”姬玄声音沙哑，“父王…怎会算法反噬？”

芈月凝眉：“齐王修的是《齐民算法》，以稳著称，按理不该…”

“除非有人动了手脚。”姬玄眼中寒光一闪，“我离城不过五日，父王就出事…太巧了。”

车外，田忌策马并行：“殿下，太医诊断，大王中的是‘递归栈溢出毒’——有人在大王修炼的算法典籍中，植入了无限递归陷阱。”

“无限递归…”姬玄闭目，脑中飞速分析，“需要《九章算法》中的‘栈帧修复术’…但第一卷中并无此术。”

芈月急道：“那怎么办？” “第二卷，”姬玄睁眼，“《九章算法》第二卷‘方程’，专解异常状态。但第二卷…在魏国算法库。”

田忌脸色一变：“魏国？庞涓的魏国？”

话音未落——

“咻咻咻！”

前方官道两侧树林，箭如雨下！

“敌袭！结阵！”田忌大吼。

三百齐兵瞬间结成圆阵，盾牌高举，箭矢叮当落下。

但这不是普通箭矢——箭头上刻着算法符文，落地即触发！

“轰！轰！轰！”

地面炸开，符文交织成巨型有向图，将车队困在中央！

姬玄掀开车帘，瞳孔骤缩。

前方官道上，庞涓摇扇而立，笑容温和如旧。他身旁站着八名黑袍阵师，各持算筹，正在构建阵法。

“庞先生，”姬玄冷冷道，“这就是魏国的待客之道？”

庞涓拱手：“七王子误会。庞某此行，是为…借《九章算法》一观。只要殿下交出玉简，立刻放行，还赠‘方程卷’救齐王。”

“若我不给呢？” “那…”庞涓笑容转冷，“只好请殿下…永远留在此地了。”

他扇子一挥：“起阵！”

八名阵师同时划动算筹，空中浮现巨大光图——

【图论杀阵·最短路径封锁】

**【描述】：以车队为起点，临淄为终点，官道为边，设权重障碍】

**【效果】：所有从起点到终点的路径，权重皆被修改为无穷大】

【实质】：让你们找不到任何可行回家之路】

姬玄瞬间看透：“你想用负权环修改边权重，使所有路径不可达？”

“殿下果然通透。”庞涓笑道，“此阵名‘狄杰斯特拉之困’——任你算法再高，找不到最短路径，就只能困死阵中。”

田忌怒吼：“庞涓！你魏国要与我齐国开战吗？！”

“开战？”庞涓摇头，“不不，这只是…算法切磋。姬玄殿下若破不了阵，便是学艺不精，死于阵中，与我魏国何干？”

他顿了顿：“当然，若殿下愿归顺魏国，庞某可亲自护送殿下回临淄，还奉上《九章算法·第二卷》。”

赤裸裸的威胁。

第二幕：破阵之思，最短路径之争

姬玄跳下马车，走向阵法边缘。

地面上的有向图复杂无比：

• 节点：三十六处关键路口
• 边：七十二段官道
• 初始权重：道路长度（已知）
• 当前权重：部分边被修改为无穷大（∞）

芈月跟上来：“此阵用狄杰斯特拉算法（Dijkstra）原理，修改边权破坏连通性…可有解法？”

“有，”姬玄盯着阵法，“狄杰斯特拉算法有两个弱点：一、不能处理负权边；二、贪心选择可能不是全局最优。”

他大脑飞转：“庞涓引入‘负权环’，让某些边权重临时变负，诱导算法走错路…但负权环本身，就是破绽。”

田忌急道：“殿下，如何破？强冲吗？”

“强冲必死，”姬玄摇头，“此阵隐含‘优先级队列’——谁先动，谁先被重点攻击。”

他盘膝坐下，取出玉笔，在地上快速推演。

第一步：建模 将三十六节点编号，七十二边列出，初始权重记为w₀。

第二步：检测负权环 “狄杰斯特拉怕负权…那就用贝尔曼-福特算法（Bellman-Ford）！”姬玄眼中精光一闪。

贝尔曼-福特可处理负权，且能检测负权环！

他快速写出算法框架：

class 路径破解 {
    int[] 最短距离;
    int[] 前驱节点;
    
    boolean 贝尔曼福特(int 节点数, 边[] 边集, int 起点) {
        最短距离 = new int[节点数];
        Arrays.fill(最短距离, Integer.MAX_VALUE);
        最短距离[起点] = 0;
        
        // 松弛操作 V-1 轮
        for (int i = 1; i < 节点数; i++) {
            for (边 e : 边集) {
                if (最短距离[e.起点] != Integer.MAX_VALUE 
                    && 最短距离[e.起点] + e.权重 < 最短距离[e.终点]) {
                    最短距离[e.终点] = 最短距离[e.起点] + e.权重;
                    前驱节点[e.终点] = e.起点;
                }
            }
        }
        
        // 检测负权环：再松弛一轮，若还能更新，则有负权环
        for (边 e : 边集) {
            if (最短距离[e.起点] != Integer.MAX_VALUE 
                && 最短距离[e.起点] + e.权重 < 最短距离[e.终点]) {
                return true; // 存在负权环
            }
        }
        return false;
    }
}

第三步：逆向利用 “检测到负权环后…”姬玄嘴角微翘，“不是消除它，而是放大它！”

• 第一章-链表分治，初露锋芒 ◀ 返回

第二章：九章迷宫，群雄逐鹿

第一幕：金光现世，秘境开启

姬玄在算法殿一战成名后的第七日。

子时三刻，万籁俱寂。

齐国稷下学宫旧址，荒废三百年的演算法坛，突然震动。

“轰隆隆——”

九道金色光柱自地底冲天而起，直破云霄！光柱在夜空中交织，竟构成九个巨大篆字：

“九章算法·第一卷”

金光映照半个临淄城，无数算法修士从梦中惊醒，披衣推窗，目瞪口呆。

“九章迷宫…开启了！” “上古算法秘境！得之可成圣人！” “快！禀报大王！”

姬玄正在府中参悟新得的《算法导论》，系统突然狂响：

【紧急！上古秘境开启！】

**【名称】：九章迷宫】

**【层级】：九层，对应《九章算法》九卷】

**【当前开启】：第一卷“方田”迷宫】

**【核心算法】：面积计算、最大子矩阵】

**【危险等级】：★★★★☆】

【传闻】：迷宫中藏有“算圣”刘徽真传】

几乎同时，侍从撞门而入：“殿下！稷下学宫异象！大王急召！”

姬玄收功睁眼，眼中闪过精光。

终于来了。

算法殿，灯火通明。

齐威王面色凝重：“九章迷宫三百年一开，每次开启，列国天骄死伤过半。但…得其中一卷者，必成一代宗师。”

他看向姬玄：“玄儿，你前日展现算法天赋，此机缘…你可愿争？”

殿内众臣神色复杂。有人嫉妒，有人担忧，有人幸灾乐祸。

姬玄拱手：“儿臣愿往。” “好！”齐威王拍案，“田忌将军率三百精兵护卫，淳于髡先生为算法顾问，七王子姬玄…为我齐国主探！”

“报——！”又一侍从冲入，“秦、楚、魏、赵、韩、燕六国使团连夜出城，皆往稷下！”

齐威王冷笑：“果然都坐不住。玄儿，此行凶险，记住——算法可输，性命要保。”

姬玄点头，心中却道：算法，我也不会输。

第二幕：迷宫入口，群雄聚首

稷下学宫旧址，已成人海。

九道光柱汇聚处，一座青铜巨门缓缓升起，门上刻满算法符文：

【九章迷宫·第一卷·方田】
【入内须知】：
1. 迷宫共九层，每层一道算法题
2. 解题正确可入下一层，错误触发机关
3. 最先抵达第九层者，得《九章算法·第一卷》
4. 生死自负，算法为凭

门前空地，列国天骄分立。

秦国阵营： 嬴驷（秦国太子）居中，商鞅立于侧，身后跟着十名黑衣算法死士。 嬴驷冷冷扫视众人：“《九章算法》乃我大秦必得之物，诸位…莫要自误。”

楚国阵营： 芈月一袭白衣，腰佩递归玉佩，身后八名楚女手持算筹阵图。 她目光扫过姬玄时，微微一顿，随即移开。

魏国阵营： 一名青衫文士摇着羽扇，正是魏国第一天才——庞涓。 他笑眯眯对姬玄拱手：“七王子殿下，前日交易，魏王已准。庞某此行…还望殿下多多关照。”

姬玄微笑还礼，心中警惕——此人笑里藏刀，史书称其“妒才”，需小心。

赵、韩、燕等国亦有高手到场，个个气息深沉。

“嗡——”

青铜巨门洞开，露出幽深通道。

商鞅突然朗声道：“既是算法比拼，何不设个彩头？哪国最先有人抵达第九层，其余六国…各输城池一座！”

全场哗然！

嬴驷接话：“可。秦国若输，割让函谷关外三城！” 芈月清冷道：“楚国若输，让出云梦泽算法秘境。” 庞涓笑道：“魏国若输…送上‘优先队列’秘法全卷。”

众人看向姬玄。

姬玄摸摸鼻子：“齐国若输…我当众承认，我是靠作弊赢的商君。”

“你！”商鞅大怒。

“开玩笑的。”姬玄正色，“齐国若输，献上‘阴阳双链诀’专利，永不再用。”

“好！”嬴驷眼中闪过贪婪，“立天道誓约！”

第一章：链表分治，初露锋芒

• ◀ 返回

第一幕：算法朝会，秦使发难

齐国，临淄城，算法殿。

晨光透过雕花木窗，在青石地面上投下斑驳光影。大殿中央，一丈见方的水镜悬浮空中，波纹流转——正是列国敬畏的“天机算法系统”。

齐威王端坐龙纹宝座，眉宇间隐现忧色。殿下文武分立两侧，左侧以宰相邹忌为首，右侧以上将军田忌为尊。

“诸位爱卿，”齐威王声音低沉，“天机系统已出今日之题。谁能解之，赏千金，封上卿！”

水镜波纹骤变，浮现金色篆文：

【王诏·链表分封令】

【场景】：秦王点兵改制，甲士营将士依序而列，各佩功勋数

【龙门线】：阈值 叁

【改制令】：功勋小于伍 者立左阵，大于等于伍者立右阵

【铁律】：左、右阵中，诸将士初始前后次序不可乱

【当前最佳解法】：秦相商鞅之’两度遍历册录法’】

“哈哈哈！”

一声长笑打破沉寂。黑袍秦使踏前一步，腰间玉佩叮当作响，正是秦国第一算法大师——商鞅。

“齐王陛下，”商鞅拱手，眼中却无半分敬意，“我大秦‘双重遍历法’，虽复杂度略高，但堂堂正正，势如破竹！不知齐国可有更高明解法？”

他袖袍一挥，水镜显现解法：

/** 
**【题目：链表分区】**

**【描述】：给定单链表头结点 head 与整数 x，请分隔链表，使所有小于 x 的节点皆在大于等于 x 的节点之前**

**【约束】：须保持节点初始相对位置**

**【当前最佳】：时间复杂度 O(n²)，空间复杂度 O(n)，提供者——秦使商鞅】**
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：
输入：head = [2,1], x = 2

输出：[1,2]

提示：

链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200
*/
// 秦国解法：双重遍历法
public ListNode partition(ListNode head, int x) {
    // 第一次遍历：收集所有小于x的节点
    List<ListNode> smallList = new ArrayList<>();
    ListNode p = head;
    while (p != null) {
        if (p.val < x) smallList.add(p);
        p = p.next;
    }
    
    // 第二次遍历：收集所有大于等于x的节点  
    List<ListNode> largeList = new ArrayList<>();
    p = head;
    while (p != null) {
        if (p.val >= x) largeList.add(p);
        p = p.next;
    }
    
    // 拼接新链表
    ListNode dummy = new ListNode(-1);
    ListNode curr = dummy;
    for (ListNode node : smallList) {
        curr.next = node;
        curr = curr.next;
    }
    for (ListNode node : largeList) {
        curr.next = node;
        curr = curr.next;
    }
    curr.next = null;
    
    return dummy.next;
}

“两次遍历，两个列表，”商鞅傲然道，“虽非最优，却稳妥可靠。此乃我大秦治国之道——步步为营，稳中求胜！”