其实很多同学第一次遇到 CodeVS 1620 轮船问题都会陷入一个误区这题看起来像个最短路甚至像个模拟题怎么就和 DP 扯上关系了我第一次刷这道题的时候也一样那时候我刚学完动态规划的基础模型什么背包、线性 DP、区间 DP 都只是“背过模板”根本没形成自己的分析框架。轮船问题题目短、输入朴素、输出也只有一个数字但它恰恰是让你把“状态设计”“最优子结构”“转移方程”这三件事真正理解透的一道好题。这篇文章就是一份完整的解题报告我会从题意开始讲清楚为什么贪心不可行状态怎么定转移方程怎么推再给完整可运行的代码和我在实际提交中踩过的坑希望能帮到正在 DP 入门路上较劲的人。1. 题目到底在问什么港口之间的直达费用与最省航线1.1 先弄清输入输出长什么样题目大意是这样的有一条航线从 1 号港口出发终点是 N 号港口途中有编号 1 到 N 的港口。你可以在任意港口下船换乘另一艘船也可以不下船直接驶向后面的港口。题目会直接告诉你从第 i 个港口到第 j 个港口i j的“直达费用”是多少。现在要求你从 1 号港口出发最终到达 N 号港口问最少要花多少钱。输入格式通常是N 接下来共有 N-1 行 第 1 行N-1 个数分别表示 1 - 21 - 3…1 - N 的费用 第 2 行N-2 个数分别表示 2 - 32 - 4…2 - N 的费用 …… 最后一行1 个数表示 N-1 - N 的费用举个例子3 5 15 7这里 N 3。第一行的 5 和 15表示从 1 号港口到 2 号港口的费用是 5从 1 号港口到 3 号港口的费用是 15第二行的 7 表示从 2 号港口到 3 号港口的费用是 7。那从 1 到 3 有两条路一条是直接买 1 到 3 的票花费 15另一条是先花 5 到 2再花 7 到 3总费用是 12。所以答案输出 12。这个例子非常小但已经透露了一个重要信号你完全可以不在中途任何港口停靠直接去终点也可以在中途换乘多次。换乘不另收手续费只按两两港口之间的直达费用来算。1.2 数据范围决定了你可以怎么“浪”CodeVS 上这题的数据范围我记得不算大N 一般不超过 200费用也都是正整数不会出现负费用。这意味着什么意味着如果你不会 DP用暴搜或者全排列枚举所有航线小数据也能过但一旦 N 变成 100、200计算量就会变成天文数字。这个数据范围也刚好是“动态规划 O(N^2)”能轻松解决的范围题目出得很有心。我建议你在读题的时候形成两个条件反射N 在 100 到 200 左右且转移关系是个 DAG只能从小编号港口到大编号港口大概率就是 DP 或最短路的题目题目给的是两两之间的费用矩阵不是邻接表那复杂度也就被限制在 O(N^2) 量级。理解清楚题意后你可以先自己动手画一画样例的港口关系图1 号能去 2、32 号能去 3。你会发现整个航行方向永远是编号从小到大不允许走回头路。这是本题可以用线性 DP 解决的大前提。1.3 一个容易被忽略的细节直达费用和转乘费用的关系我再强调一下题目给的是“任意两个港口之间的直达费用”。这个费用只在你坐了某一趟船的时候发生。如果你选择在中间港口转一圈哪怕只隔一个港口也要把两段费用加起来。这就是为什么样例中 1 - 3 的直达费 15 比 1 - 2 - 3 加起来 12 更贵但你不能因为 1 - 3 是直达就认为它一定更优。题目的本质是求一条从 1 到 N 的路径使得路径上所有边权之和最小。很多同学第一次看到这里会想这不就是最短路吗直接用 Floyd 或者 Dijkstra 不就行了确实从建模角度上它等价于求 DAG 上的最短路但既然是放在 DP 专题里就必须用 DP 的思路去重新推导一遍。这个过程能帮你培养“从最后一步往前拆”的直觉而这种直觉在做更多区间 DP、树形 DP 时至关重要。2. 别急着写代码为什么贪心和全排列都撑不住2.1 贪心最大的问题是你总以为自己看得够远拿到轮船问题最容易产生的错误思路是每次到一个港口都选“当前能到达的港口中费用最便宜”的那个走。这个策略听起来好像挺聪明既然 1 - 2 只要 51 - 3 要 15那肯定先到 2 再说。但后面如果 2 - 4 要花 100而 3 - 4 只要 1那么全局最优是 1 - 3 - 4花费 16贪心却会走 1 - 2 - 4花费 105。这就是贪心失效的典型原因你做决策时只考虑了当前这一步的“局部最优”没有考虑这一步对后续路径费用的影响。在最短路径类问题里边权只会让当前选择影响到后面的所有选择所以简单的贪心通常不是可靠方案除非这个问题满足很强的贪心性质比如“任意前缀最优等价于全局最优”但轮船问题显然不满足。我当初还试过另一个变种贪心每次比较“直接到终点”和“先到中间某个港口再到终点”的费用选一个总费用更小的方案。这个思路在样例里能过但一旦 N 变大你会发现自己根本不知道该从哪一个“中间港口”作为比较基准反复比较最终变成了变相枚举复杂度并没有降下来。2.2 全排列枚举所有航线为什么会爆炸另一种朴素想法是把所有可行的停靠方案都列出来然后逐条计算总费用。从 2 号到 N-1 号港口每一个港口都有两种选择停靠或不停靠。因此航线的总数是 2^(N-2)当 N20 时已经超过 26 万条N30 时达到 2.68 亿条完全跑不动。你可能会说那我用 DFS 枚举所有路径一条条搜不是更聪明吗其实 DFS 枚举的本质也是指数级因为从一个港口出发理论上可以跳到任何后面的港口路径组合非常多。在没有剪枝的情况下N200 的规模会让程序跑到天荒地老。这个“枚举组合数爆炸”的现象在 DP 题里特别常见它实际上在提醒你如果一个状态的答案只依赖于前面的某些状态而不是依赖于一条完整的历史路径那么你就不需要把整条路径枚举出来只需要记录“到达这个状态的最小代价”就够了。这正是 DP 的核心思想用状态去压掉重复计算的子问题。2.3 拆开最后一段就看到了最优子结构我们来看一个关键观察假设从 1 号港口到 N 号港口最优航线的倒数第二站是 k1 ≤ k N。那么这条最优航线可以分成两段1 号港口到 k 号港口以及 k 号港口到 N 号港口。如果从 1 到 k 还有一条比当前路径更便宜的选择那我把最优航线里的前一段换成那条更便宜的选择整个从 1 到 N 的费用就会变得更小。这与“当前航线是全局最优”矛盾。因此全局最优航线中的任意前缀也一定是从起点到该中间港口的最优航线。这个性质就是动态规划里常说的“最优子结构”。很多人背概念觉得抽象其实放到轮船问题上非常好懂如果前半段不是最优的你完全可以把它替换掉让总费用更小所以最优解的内部一定是由若干个子问题的最优解组成的。有了最优子结构我们就可以大胆设计状态了让 f[i] 表示“从 1 号港口到 i 号港口的最少费用”。只要 i 之前的每个 f[j] 都算对了那么 f[i] 就可以只考虑最后一段从 j 到 i 的直达费用不需要关心 j 之前到底是怎么走的。这就是 DP 能代替暴搜的根本原因。3. DP 状态与转移从最后一段下手化整为零3.1 状态定义f[i] 表示从 1 到 i 的最少费用我们定义f[i]从 1 号港口出发最终到达 i 号港口所需的最少费用cost[i][j]从 i 号港口直达 j 号港口i j的费用。边界条件是 f[1] 0因为船一开始就在 1 号港口不需要花钱。对于 i 从 2 到 N我们想计算 f[i]。怎么算还是抓住“最后一段”这个视角想要最终停在 i 号港口那上一步一定停在某个 j 号港口满足 1 ≤ j i。你从 j 港直接乘船到 i 港支付的费用是 cost[j][i]。已经花掉的前半段费用就是 f[j]。于是f[i] min( f[j] cost[j][i] )其中 j 取遍 1 到 i-1。这就是转移方程。你可能会问为什么只需要枚举最后一个中转港口 j因为从 1 到 j 这一段不管内部停靠多少次它的最少费用已经被 f[j] 记录下来了。你不需要知道 f[j] 对应哪条具体航线只需要拿这个最优值参与后续计算。3.2 转移方程的两个直观理解方式第一种理解从“终点往前看”。我要求到 i总是从某个 j 跳过来的所以把所有可能的 j 试一遍取最小。第二种理解从“起点往后看”。当我算完了 f[j]就可以用它去更新所有后面的港口 f[i]if (f[j] cost[j][i] f[i]) 则更新 f[i]。这个“松弛”操作和最短路算法里的松弛特别像因为它本来就是一个 DAG 最短路问题。两种理解方式没有本质区别写代码时正推倒推都能写。我个人更喜欢“往后更新”的写法因为它比较好调试外层循环从 1 到 N每算完一个 f[j]就立刻检查它到后面所有港口 i 的路径是否更便宜。这样代码非常直观而且在之后写背包问题时你会发现这种“用已知状态去更新未知状态”的思路极其常见。3.3 初始化、循环顺序和答案输出初始化时f[1] 0其余 f[i] 全部设成一个很大的数比如 0x3f3f3f3f 或者 1e9。这个“很大”必须大到不会影响答案但又不能大到在加法运算时让整型溢出。一般竞赛里常用的技巧是 memset(f, 0x3f, sizeof(f))因为 0x3f3f3f3f 加上另一个 0x3f3f3f3f 也不会溢出 int 的 32 位上限这是个很方便的细节。循环顺序上有一个硬性要求计算 f[i] 时所有可能被用到的 f[j] 都必须已经算好了。由于 j 一定小于 i所以我们只需要保证外层 i 从小到大枚举即可。也就是说从 i 2 循环到 N内层 j 1 循环到 i - 1一定不会出现“用未计算的 f[j] 去更新状态”的情况。这点看似简单但如果你直接用记忆化搜索写反而容易忽略循环顺序的依赖关系。最后的答案就是 f[N]直接输出即可。如果 N 1那起点就是终点费用为 0这个边界也要考虑。3.4 正推写法与记忆化搜索的等价性很多教材喜欢给正推代码因为数组下标直观。但我也想提一下记忆化搜索版本它能帮你验证自己的状态设计是否合理。你写一个函数 dfs(i)表示求 f[i]递归地遍历所有 j i返回 min(dfs(j) cost[j][i])。只要用 memo 数组记录已经算过的状态复杂度同样是 O(N^2)。这个版本的好处是不用担心循环顺序缺点是递归开销大一些而且对“状态依赖关系”的理解不够直观时容易写得像暴力模拟。实际做题时两种方法你可以都写一遍然后对拍。我就是这样确认自己的转移方程没有写错的这个方法在刷任何 DP 题时都很好用。4. 代码实现标准二维数组写法 空间优化写法4.1 C 标准写法二维费用矩阵#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int MAXN 205; int cost[MAXN][MAXN]; int f[MAXN]; int main() { int n; cin n; // 读入上三角费用矩阵 for (int i 1; i n - 1; i) { for (int j i 1; j n; j) { cin cost[i][j]; } } // 初始化 memset(f, 0x3f, sizeof(f)); f[1] 0; // DP从 1 号港口出发逐步计算到每个港口的最少费用 for (int i 1; i n; i) { for (int j i 1; j n; j) { if (f[i] cost[i][j] f[j]) { f[j] f[i] cost[i][j]; } } } cout f[n] endl; return 0; }这段代码里外层循环是 i内层循环是 j。当 i 固定时f[i] 已经被前面的更新确定了所以可以用它去刷新所有 j i 的 f[j]。这个写法从“源点推进”的角度思考本质上和 Dijkstra 的更新方式很像只是这里天然按编号顺序推进不需要优先队列。你也可以把 DP 改成“从终点回推”的写法for (int i 2; i n; i) { for (int j 1; j i; j) { f[i] min(f[i], f[j] cost[j][i]); } }两种写法结果完全一致但要注意别混合使用否则容易绕晕。4.2 读入上三角矩阵的注意事项输入时 cost[i][j] 只在 i j 的时候存在所以读取用的是for (int i 1; i n - 1; i) { for (int j i 1; j n; j) { cin cost[i][j]; } }千万不要顺手写成for (int i 1; i n; i) { for (int j 1; j n; j) { cin cost[i][j]; } }因为输入里根本没有 N 行 N 列那么多数据这样会直接让你的程序等待输入或者读入错位最终要么超时要么答案全乱。这个细节我在第一次提交时就掉坑里了后面会专门再说。4.3 Python 写法参考如果你用 Python 刷题代码可以这样写def solve(): n int(input()) cost [[0] * (n 1) for _ in range(n 1)] for i in range(1, n): row list(map(int, input().split())) # row 的长度是 n - i for idx, val in enumerate(row): j i 1 idx cost[i][j] val INF 10 ** 18 f [INF] * (n 1) f[1] 0 for i in range(1, n 1): for j in range(i 1, n 1): if f[i] cost[i][j] f[j]: f[j] f[i] cost[i][j] print(f[n]) solve()要注意 Python 读入上三角矩阵时每一行的数字个数不一样不能简单用一个 n×n 的矩阵就一次性读满。我这里用row拿到当前行的所有数然后根据i的位置映射到对应的列号这样就不会错位。4.4 能不能省掉 cost 二维数组有些同学会问题目必须把整个费用矩阵读进来吗能不能读一行算一行省个空间理论上可以但会比较别扭。因为当我们计算 f[i] 的时候需要知道所有 j i 到 i 的费用而这些费用分散在输入的不同行里不一定刚好在读入顺序上能立刻用到。如果你确实想省内存可以改变 DP 顺序采用“读入一段更新一段”的方式先读入所有从 1 号出发到后面港口的费用更新 f再读入从 2 号出发的再更新。这样空间可以降到 O(N)只保留一维 f 数组。但代码可读性会下降对于 N 200 的题目完全没有必要。一般来说竞赛里不推荐为了几十 KB 的内存牺牲编码清晰度。5. 测样例、查边界我当年踩过的几个坑5.1 把上三角矩阵读成下三角或者对称矩阵这个问题我在前面已经提到过但还是要单独拿出来说因为它实在太常见了。题目输入的费用是“只给 i j 的情况”也就是一个上三角矩阵。如果你的代码写成for (int i 1; i n; i) { for (int j 1; j n; j) { cin cost[i][j]; } }当 N3 时实际输入只有 5、15、7 这三个数而你的代码会尝试读 9 个数于是后面的读取就会错乱程序等不到完整输入或者把换行符当成数字结果不可预测。正确的做法是必须按照行长度递减的方式读入。我建议在本地测试时把样例输入贴进去后先用一个临时变量把 cost 矩阵打出来检查一遍确认cost[1][3] 15、cost[2][3] 7再往下做。这种“输入即对齐”的习惯能省下大量排错时间。5.2 初始化用 INT_MAX 导致加法溢出另一个很典型的坑是状态数组初始化int f[MAXN]; for (int i 1; i n; i) f[i] INT_MAX; f[1] 0;然后计算 f[j] f[i] cost[i][j] 时如果 f[i] 还是 INT_MAX加一个正数就会溢出成负数导致你得到一堆莫名其妙的负值。虽然题目数据不一定能触发但这种写法本质上是错的属于“在错误的代码上碰巧过了样例”。我习惯用memset(f, 0x3f, sizeof(f))这样每个 int 变成 0x3f3f3f3f大约是 10 亿出头再加上一个正常费用也不会超过 int 上限。如果你用 printf 调试看到状态数组里全是 1061109567那说明这些状态还没被更新很重要。5.3 循环顺序写反导致使用了没算完的状态如果你采用“回推”写法一定要写成for (int i 2; i n; i) { for (int j 1; j i; j) { f[i] min(f[i], f[j] cost[j][i]); } }不能写成for (int i 1; i n; i) { for (int j n; j i; j--) { f[j] min(f[j], f[i] cost[i][j]); } }第二种写法看似也是从前往后的但如果 i 还在循环中f[i] 可能被后面的更新再次改变导致同一个转移被执行多次虽然本例中因为状态天然是从小到大更新的问题不大但在其他 DP 题里随意的循环顺序可能造成重复更新甚至状态回环。正确做法是回推写法必须保证内层 j 严格小于外层 i正推写法可以写成“用 f[i] 更新所有 j i”两种任选一种不要混搭。5.4 边界值测试N1 和 N2很多同学写完代码只测样例就交了结果遇到 N1 时直接数组越界或者输出 0 都做不到。N1 意味着起点就是终点答案当然是 0。上面给的代码并不会对 N1 做什么特殊处理因为读入循环for (int i 1; i n - 1; i)一次都不会执行f[1] 还是 0最终输出 f[1] 0完美通过。N2 时只有 1-2 一笔直达费用答案就是 cost[1][2]程序也能正确处理。这两个边界虽然简单却能帮你发现读入和输出是否有低级错误我每次写完都会专门测一下。5.5 用手算样例验证每一步状态调试 DP 题有一个笨但极其有效的方法把每次状态更新后的 f 数组打印出来。对于样例你应当看到初始时 f[1]0f[2]5f[3] 一开始是 15后来被 1-2-3 更新成 12。如果你打印出来的 f[3] 还是 15那就说明你在更新时根本没用到 f[2] 已经从 0 更新到了 5。这种排查方法比盯着代码看十分钟更高效。6. 从轮船问题延伸出去的 DP 模型6.1 如果题目要求输出具体航线有些变种题不只要输出最少费用还要输出途经的港口。这时你可以在更新 f[j] 时顺便记录 pre[j] i表示最优方案里到达 j 之前的那个港口是 i。计算完成后从 N 一路回溯到 1再把路径倒序输出即可。核心代码大概是int pre[MAXN]; // 更新时 if (f[i] cost[i][j] f[j]) { f[j] f[i] cost[i][j]; pre[j] i; } // 输出时 vectorint path; for (int cur n; cur ! 1; cur pre[cur]) { path.push_back(cur); } path.push_back(1); reverse(path.begin(), path.end()); for (int x : path) cout x ;这个变形能让你更强烈地意识到DP 并不只是为了求一个数值它其实把整条最优路径的信息都隐式地算出来了只是我们平时没有把它存下来而已。6.2 如果要求必须经过某些港口比如题目改成“必须经过港口 3 和港口 7”那就变成了分段最短路先算 1 到 3、3 到 7、7 到 N 的最少费用再加起来。由于每个子问题都还是经典的轮船问题直接重复三次 DP 即可。如果必经港口数量很多或者存在顺序限制就可能要用到状态压缩 DP比如把“当前在哪个港口已经访问过哪些必经港口”压缩成状态复杂度会高很多。但万变不离其宗你还是需要先掌握最基础的 f[i] 定义才能在这些变形题里灵活扩展。6.3 与 Dijkstra、Floyd 的联系轮船问题有一个很强的特殊性所有边都是从小编号港口指向大编号港口形成一张有向无环图DAG。DAG 上求最短路本来就可以用拓扑序 DP 求解复杂度 O(N^2) 和本题几乎一样。如果去掉“只能从小号到大号”的限制变成任意两个港口之间都可以互相航行那问题就变成了普通有向图最短路DP 就不能随便用了得用 Dijkstra 或 Floyd。这里有个很值得思考的点为什么 DAG 可以用 DP 解决因为存在一种拓扑顺序使得所有依赖都在之前被算好而在普通图里状态之间可能有环你就需要迭代多次才能稳定。理解这一点之后你会对整个 DP 产生新的认识DP 并不是一类神奇技巧它本质上就是在一个无环依赖关系图上的递推。你只要能把大问题拆成若干有依赖顺序的小问题并且小问题的最优解能组合成大问题的最优解就可以 DP。6.4 类似题目与练习建议如果你想巩固这类“线性 DP / 序列最短路”的感觉可以去做做这几个题P1359 租用游艇和轮船问题几乎一模一样就是换个故事背景P1113 杂务DAG 上求最长/最短完成时间的 DPP1800 software_NOI导刊2010提高07更复杂的阶段划分 DP一些最短路题比如 P4779 单源最短路径标准版虽然用的是 Dijkstra但你能对比出 DAG 和普通图的处理差异。练习的时候不要只 AC 就完事建议你每做一题都回答三个问题状态是什么转移依赖哪些之前的子问题这个依赖关系是不是无环的如果三问都能清楚回答那你的 DP 基础就算真正打牢了。我个人在实际做题时有个习惯拿到一道 DP 题不管会不会先用记忆化搜索把暴力递推写出来再用迭代 DP 去改。在轮船问题上这个流程能让我花不到十分钟就把状态定义、边界条件、转移方程全部理清。等你把这个流程跑熟了再看到那些花里胡哨的区间 DP、树形 DP无非就是状态数组多了几维、依赖关系复杂了一点底层思路还是一样的。希望这份解题报告能让你少走我当年走过的弯路。