动态规划实战：从“画廊”问题解析双序列最优路径算法

1. 项目概述从“画廊”到“动态规划”的解题心路最近在整理过去的算法竞赛笔记翻到了第十一届蓝桥杯国赛Java大学C组的一道题目名字就叫“画廊”。这题目名字听起来挺文艺但内核却是一个经典的动态规划问题考察的是在特定约束下的最优路径规划。我记得当时在赛场上不少同学被这个看似“艺术”的标题迷惑了没能在第一时间抓住问题的本质导致时间紧张。今天我就以这道题为例深入拆解一下如何将实际问题抽象为动态规划模型并分享一些在竞赛中快速识别和解决此类问题的实战技巧。无论你是正在备赛的选手还是对算法感兴趣的开发者相信这篇从问题理解到代码实现的完整复盘都能给你带来一些启发。这道题的核心场景可以这样理解我们有一条长长的走廊画廊走廊的两侧墙壁上挂着许多画作。你作为一名管理员需要从走廊的一端出发检查所有的画作最终到达另一端的出口。检查画作需要你走到画作的正前方因此你需要在左右两侧的墙壁之间来回移动。问题目标是找到一条总距离最短的路径让你检查完所有画作并成功离开。这本质上就是一个双序列、带状态的最优路径问题动态规划正是解决它的利器。2. 问题核心与数学模型抽象2.1 题意解析与关键约束首先我们需要把题目描述转化为清晰的数学模型。假设走廊是笔直的我们将其简化为一维数轴。左侧墙壁上的画作位置记为数组L[1...l]右侧墙壁上的画作位置记为数组R[1...r]。你从起点S例如左侧的入口坐标为(0, 0)假设左侧为0右侧为1坐标轴沿走廊方向出发最终必须到达终点T例如右侧的出口坐标为(走廊长度, 1)。关键约束如下检查顺序画作的检查顺序是固定的吗通常在这类问题中画作可以按任意顺序检查但每个画作必须且仅被检查一次。这给了我们规划路径的自由度也是优化的关键。移动方式你只能在走廊中行走。从左侧一点移动到右侧一点需要横向穿过走廊假设走廊宽度为w同时纵向位置也可能变化。两点间的距离就是欧几里得距离。状态定义在任意时刻你的“状态”由哪些因素决定显然你已经检查了哪些画作是核心。但由于画作数量可能达到200甚至更多用二进制掩码表示检查状态状态空间为2^n是不可行的。我们需要发现更高效的状态定义。经过分析一个常见的有效状态定义是dp[i][j][side]。其中i表示已经检查了左侧墙壁的前i幅画按位置从左到右排序。j表示已经检查了右侧墙壁的前j幅画。side表示你当前所处的位置在左侧0还是右侧1。这个状态定义的精妙之处在于它利用了“最优子结构”的特性为了达到状态(i, j, side)你的上一步一定来自于状态(i-1, j, 0/1)或(i, j-1, 0/1)即你刚刚检查完左侧第i幅画或右侧第j幅画。这样我们就把指数级的状态压缩成了O(l*r*2)的规模。2.2 状态转移方程推导设dist(a_side, a_pos, b_side, b_pos)为从位于a_side侧、纵向位置a_pos的点移动到b_side侧、纵向位置b_pos的点的直线距离。那么状态转移方程可以如下建立当前在左侧 (side0)且刚刚检查完左侧第i幅画上一个状态可能是在左侧检查完第i-1幅画后直接走到第i幅画。即从(i-1, j, 0)转移来移动距离为dist(0, L[i-1], 0, L[i])。上一个状态也可能是在右侧检查完第j幅画后穿过走廊走到左侧第i幅画。即从(i-1, j, 1)转移来移动距离为dist(1, R[j], 0, L[i])。因此dp[i][j][0] min(dp[i-1][j][0] dist(0, L[i-1], 0, L[i]), dp[i-1][j][1] dist(1, R[j], 0, L[i]))当前在右侧 (side1)且刚刚检查完右侧第j幅画同理dp[i][j][1] min(dp[i][j-1][1] dist(1, R[j-1], 1, R[j]), dp[i][j-1][0] dist(0, L[i], 1, R[j]))边界条件初始化dp[0][0][0] 0起点在左侧入口假设入口位置在左侧墙壁的起点如L[0] 0。dp[0][0][1] w如果起点在左侧但第一步直接去右侧第一幅画距离是走廊宽度w假设入口在左侧0坐标右侧第一幅画在0坐标则垂直距离为w。但通常我们定义起点状态为(0,0,0)从起点到第一个检查的画作的距离在第一次转移时单独计算会更清晰。一种更清晰的初始化是dp[1][0][0] dist(起点, (0, L[1]))起点到左侧第一幅画dp[0][1][1] dist(起点, (1, R[1]))起点到右侧第一幅画其他dp[i][j][side]初始化为无穷大。最终答案 检查完所有画作后即状态达到(l, r, 0)或(l, r, 1)我们还需要走到终点T。所以最终答案是min(dp[l][r][0] dist(0, L[l], 终点), dp[l][r][1] dist(1, R[r], 终点))注意这里的L[i]和R[j]在实际编程中通常使用1-based索引并可能将起点和终点的坐标也并入数组或单独处理以简化距离计算。务必在编码前明确每个下标的具体含义。3. 算法实现细节与代码剖析理解了状态定义和转移方程后我们来看具体的代码实现。这里使用Java语言并附上详细的注释。3.1 数据结构与输入处理首先我们需要读取画廊长度、走廊宽度、左右两侧画作的数量和位置。画作位置通常是无序输入的我们需要先进行排序因为我们的状态定义依赖于“前i幅画”是有序的。import java.util.Arrays; import java.util.Scanner; public class Gallery { public static void main(String[] args) { Scanner sc new Scanner(System.in); int l sc.nextInt(); // 左侧画作数量 int r sc.nextInt(); // 右侧画作数量 double length sc.nextDouble(); // 画廊长度纵向 double width sc.nextDouble(); // 走廊宽度横向 double[] L new double[l 2]; // 多出两个位置0存放起点l1存放终点这里需根据题意调整 double[] R new double[r 2]; // 假设起点在左侧0坐标终点在右侧length坐标 L[0] 0.0; // 起点纵坐标 R[0] 0.0; // 右侧起点不一定需要看建模 // 更常见的建模单独记录起点(0,0)和终点(length, width侧) // 画作下标从1到l, 1到r for (int i 1; i l; i) L[i] sc.nextDouble(); for (int i 1; i r; i) R[i] sc.nextDouble(); Arrays.sort(L, 1, l 1); // 对画作位置排序 Arrays.sort(R, 1, r 1); // 接下来是DP数组 dp[i][j][0] 和 dp[i][j][1] double[][][] dp new double[l 1][r 1][2]; // 初始化所有值为无穷大 for (int i 0; i l; i) { for (int j 0; j r; j) { dp[i][j][0] dp[i][j][1] Double.MAX_VALUE; } } // 初始化起点状态 // 方式一从起点直接到第一个画作 // 这种方式下dp[0][0][0]可以视为0然后第一次转移就是起点到第一个画作 // 但我们的状态定义是“检查完前i/j幅画后位于某侧”所以dp[0][0][0]0是合理的表示在起点还没检查任何画。 dp[0][0][0] 0.0; // 位于左侧起点 // dp[0][0][1] width; // 如果起点可以直接在右侧这不符合起点在左侧的假设。所以保持INF。 // 计算距离的辅助函数 // 计算从(side1, pos1) 到 (side2, pos2)的直线距离 // side: 0左1右 double w width; java.util.function.BiFunctionDouble, Double, Double dist (pos1, pos2) - { double dy pos2 - pos1; return Math.sqrt(dy * dy); }; // 更完整的距离函数考虑横向移动 double distBetween(int side1, double pos1, int side2, double pos2) { double dx (side1 side2) ? 0 : w; double dy pos2 - pos1; return Math.sqrt(dx * dx dy * dy); } } }3.2 动态规划核心循环这是整个算法的核心。我们需要按一定的顺序填充dp数组。由于dp[i][j]依赖于dp[i-1][j]和dp[i][j-1]我们可以使用双重循环i从0到lj从0到r。但要小心处理i0或j0的边界情况。// 假设我们已经有了distBetween函数和初始化好的L, R, w, dp数组 for (int i 0; i l; i) { for (int j 0; j r; j) { if (i 0 j 0) continue; // 起点状态已初始化 // 状态转移当前位于左侧 (side0)意味着刚刚检查完左侧第i幅画 if (i 0) { // 情况1: 上一个检查的画也是左侧的从左侧第i-1幅画走来 if (i-1 0) { double cost dp[i-1][j][0] distBetween(0, L[i-1], 0, L[i]); dp[i][j][0] Math.min(dp[i][j][0], cost); } // 情况2: 上一个检查的画是右侧的从右侧第j幅画走来 if (j 0) { // j可以是0表示从右侧还没检查任何画的状态转移这需要定义dp[i][0][1]的意义。 // 这里有个关键点dp[i-1][j][1] 表示检查完左侧i-1幅、右侧j幅后位于右侧。 // 如果j0表示右侧一幅都没检查那么“位于右侧”的状态是否合法 // 这取决于初始化。如果我们允许从起点直接走到右侧第一幅画那么dp[0][1][1]应该被初始化。 // 更通用的写法是在转移时如果来源状态是有效的非无穷大才进行转移。 if (dp[i-1][j][1] Double.MAX_VALUE / 2) { double cost dp[i-1][j][1] distBetween(1, R[j], 0, L[i]); dp[i][j][0] Math.min(dp[i][j][0], cost); } } } // 状态转移当前位于右侧 (side1)意味着刚刚检查完右侧第j幅画 if (j 0) { // 情况1: 上一个检查的画也是右侧的 if (j-1 0) { double cost dp[i][j-1][1] distBetween(1, R[j-1], 1, R[j]); dp[i][j][1] Math.min(dp[i][j][1], cost); } // 情况2: 上一个检查的画是左侧的 if (i 0) { if (dp[i][j-1][0] Double.MAX_VALUE / 2) { double cost dp[i][j-1][0] distBetween(0, L[i], 1, R[j]); dp[i][j][1] Math.min(dp[i][j][1], cost); } } } } }3.3 处理起点与终点的衔接上面的循环处理了检查画作的过程。我们还需要处理从起点到第一个画作以及从最后一个画作到终点的距离。一种更清晰的方法是在初始化dp时就处理好起点到第一个画作的状态// 初始化从起点(左侧坐标0)到左侧第一幅画 if (l 0) { dp[1][0][0] distBetween(0, 0.0, 0, L[1]); // 起点在左侧0坐标 } // 初始化从起点到右侧第一幅画 if (r 0) { dp[0][1][1] distBetween(0, 0.0, 1, R[1]); // 从左侧起点到右侧第一幅画 } // 注意此时dp[0][0][0]仍然可以是0作为虚拟的起点状态。 // 然后DP循环从 i0..l, j0..r但在转移时i和j至少一个大于0。 // 对于dp[1][0][0]它可以通过dp[0][0][0]转移得到所以我们也可以在循环中统一处理只要初始化好dp[0][0][0]0。 // 但dp[0][1][1]无法从dp[0][0][?]得到因为横向移动了。所以必须单独初始化或者在循环中特殊判断。对于终点假设终点位于右侧墙壁的末端坐标为length。那么最终答案是double ans Double.MAX_VALUE; // 检查完所有画后位于左侧 if (dp[l][r][0] Double.MAX_VALUE / 2) { ans Math.min(ans, dp[l][r][0] distBetween(0, L[l], 1, length)); // 从左侧最后位置走到右侧终点 } // 检查完所有画后位于右侧 if (dp[l][r][1] Double.MAX_VALUE / 2) { ans Math.min(ans, dp[l][r][1] distBetween(1, R[r], 1, length)); // 从右侧最后位置走到右侧终点在同侧横向距离为0 } System.out.printf(%.2f\n, ans); // 通常要求保留两位小数实操心得在竞赛中实现此类DP最容易出错的就是下标处理和边界初始化。建议在编码前在纸上画一个简单的例子比如左右各2幅画手动推导一下dp数组应该是什么值然后用你的程序跑一遍对比结果。另外对于距离计算要特别注意画作位置数组的索引是0-based还是1-based以及起点/终点坐标的代入。使用Double.MAX_VALUE表示无穷大时在比较和相加时要注意避免溢出可以用Double.MAX_VALUE / 2来判断。4. 算法优化与思维延伸4.1 空间优化技巧我们的DP状态是dp[i][j][2]空间复杂度为O(l*r)。如果l和r都在几百的量级这是可以接受的。但在一些极端情况下或许需要考虑空间优化。注意到dp[i][j]只依赖于dp[i-1][j]和dp[i][j-1]这是典型的可以用滚动数组优化的二维DP。我们可以将空间优化到O(r*2)或O(l*2)。例如按i递增的顺序循环我们只需要维护两行上一行i-1和当前行i。double[][] dp new double[r 1][2]; // 第一维是j第二维是side // 初始化dp数组为INF // 初始化起点状态dp[0][0] 0; (对应i0, j0, side0) // 我们需要一个额外的数组 prevDP 来保存上一行的结果 for (int i 0; i l; i) { double[][] curDP new double[r 1][2]; for (int j 0; j r; j) { Arrays.fill(curDP[j], Double.MAX_VALUE); } for (int j 0; j r; j) { // 计算 curDP[j][0] 和 curDP[j][1]需要用到 prevDP (即i-1行的dp) 和 curDP本身同一行左边的j-1 // 注意当i0时prevDP代表的是i-1行所有状态应为INF除了可能的起点状态需要特殊处理。 } // 将curDP赋值给dp作为下一轮的prevDP }滚动数组的实现会稍微复杂一些因为转移同时依赖“上一行”和“左边一格”。需要仔细处理遍历顺序和临时状态。在竞赛时间紧张时如果原始空间复杂度可以接受优先保证正确性更为重要。4.2 变种问题与思维拓展“画廊”问题是一个很好的动态规划教学案例。我们可以思考它的几种变种检查顺序强制如果画作必须按照某个预定的顺序检查比如按照创作年代那么问题就变成了一个简单的路径计算因为顺序固定没有选择余地只需要模拟路径求和即可。画廊有拐角二维平面如果画廊不是一条直线而是有拐角的L形甚至更复杂的形状画作分布在不同的墙壁上。这需要将问题扩展到二维平面上的路径规划状态定义可能需要包含二维坐标或者分段处理难度会大大增加可能需要用图论中的最短路径算法如Dijkstra。多人检查如果有多名管理员同时检查要求最小化最后一个人结束的时间最小化完成时间。这就变成了一个调度问题可能涉及动态规划、贪心甚至网络流。带时间窗口每幅画只能在特定的时间段内检查。这引入了时间维度状态可能需要增加时间信息或者转化为带约束的最短路径问题。理解基础模型后面对变种才能快速抓住核心判断是修改状态定义、增加状态维度还是需要更换算法范式。5. 竞赛实战中的常见“坑”与调试策略5.1 精度问题本题涉及浮点数运算和距离计算最终结果可能需要保留小数。常见的“坑”有使用float代替double在算法竞赛中除非内存极其紧张否则一律使用double。float的精度不足在多次运算后累积误差可能导致比较出错。直接比较浮点数相等不要用比较浮点数。判断两个浮点数是否“足够接近”应使用Math.abs(a - b) 1e-8这样的方式。输出格式严格按照题目要求输出小数位数通常使用System.out.printf(“%.2f”, ans)或DecimalFormat。5.2 初始化与边界状态这是DP出错的重灾区。起点状态明确起点是单独的一个点还是与某个画作重合。dp[0][0][0]或dp[0][0][1]究竟代表什么是否合法无效状态例如dp[i][0][1]表示检查了左侧i幅画、右侧0幅画后却站在右侧。这通常是不合法的除非起点可以直接到右侧应用无穷大表示。数组下标越界在转移时访问L[i-1]、R[j-1]要确保i-1 0和j-1 0。在循环中对i0或j0的情况要单独处理或跳过。5.3 调试方法当程序结果不对时可以按以下步骤排查小数据测试构造一个最简单的例子比如左右各1幅画走廊宽度和长度都设为容易心算的值比如宽度1长度10画作在5的位置。手动计算最短路径与程序输出对比。打印DP表在循环中打印出dp[i][j][0]和dp[i][j][1]的值与手动推导的表格对比。这是最有效的调试手段。检查距离计算函数单独测试distBetween函数确保它计算欧几里得距离的公式正确特别是处理横向宽度时。验证最终答案计算确保在加上从最后位置到终点的距离时使用的是正确的坐标和侧边。5.4 性能考量对于本题规模画作数量通常200以内O(l*r)的DP完全足够。但在一些极端输入下比如画作位置非常分散需要注意Java的输入输出效率。可以使用BufferedReader和StreamTokenizer替代Scanner来加速大量数据的读取。最后分享一个我个人在解决这类双序列DP问题时的习惯先画状态转移图。在纸上画出网格每个格子(i, j)有两个节点代表左侧和右侧然后画出所有可能的转移边从(i-1, j)或(i, j-1)过来。这幅图能极大地帮助理清状态之间的关系避免在转移方程中漏掉情况。对于“画廊”这道题这个习惯让我在编码时几乎一次就写对了核心循环。