从作业题看动态规划：电梯调度与坦克作战的算法拆解

在计算机科学的算法课程中，动态规划（Dynamic Programming, DP）往往是一个分水岭。它不像贪心算法那样直观，也不像回溯法那样暴力直接，而是需要在“状态定义”和“转移方程”之间找到微妙的平衡。最近重温了 Computer Science 320SC 课程中的经典编程作业，其中两道题目——“摩天大楼电梯调度”与“坦克消灭敌人”，非常具有代表性。前者考察线性 DP 的极致优化，后者则是区间 DP 的经典变体。对于正在备战面试或修读高阶算法课的开发者来说，吃透这两道题的逻辑，比单纯背诵模板要有价值得多。

本文将剥离掉具体的作业提交要求，专注于算法本身的推导过程，看看如何从暴力搜索的思维陷阱中跳出来，构建出高效的状态转移模型。

摩天大楼电梯问题：线性 DP 与 O(n) 优化

第一个场景设定非常生活化：你站在一座摩天大楼的底层（第 0 层），你的伙伴在顶层（第 n-1 层）等你。大楼里有一部特殊的电梯，当你位于第i层时，这部电梯可以带你到达[i+1, i+L[i]]之间的任意一层，其中L[i]是该层电梯的最大容量。每次使用电梯的成本固定为 1。目标很明确：用最少的次数到达顶层。

状态定义的直觉与误区

拿到这个问题，第一反应往往是广度优先搜索（BFS）。毕竟这是一个求“最短路径”的问题，把每一层看作图的一个节点，能到达的楼层连上边，跑一遍 BFS 确实能得到答案。但是，如果楼层数n达到十万甚至百万级别，建图的边数可能会爆炸，导致内存溢出或超时。

我们需要用动态规划的视角重新审视。定义dp[i]为从第 0 层到达第i层所需的最小电梯使用次数。我们的目标是求dp[n-1]。

最朴素的状态转移方程是这样的：
dp[i]=min⁡(dp[j])+1dp[i] = \min(dp[j]) + 1dp[i]=min(dp[j])+1
其中j是所有能一步跳到i的楼层，即满足j < i且j + L[j] >= i。

如果直接按照这个方程写代码，对于每一个i，我们都需要向前遍历所有可能的j。在最坏情况下（比如每层电梯只能坐一层），时间复杂度会退化到O(n2)O(n^2)O(n2)。在作业设定的测试用例中，n高达 1,000,000，O(n2)O(n^2)O(n2)的算法绝对无法通过自动评分器（Automarker）的时间限制。

贪心策略与滑动窗口的结合

仔细观察题目特性，我们会发现一个关键点：我们并不关心具体是从哪个j跳过来的，只关心在能跳到当前位置的所有j中，谁的dp[j]最小。

这就引出了一个优化的思路。当我们从左向右遍历楼层时，实际上是在维护一个“可达范围”。假设当前我们处于某个状态，已经计算出了前i层的最优解。对于第i+1层，哪些楼层能到达它？是所有满足k + L[k] >= i+1的楼层k。

这里有一个更巧妙的视角转换：与其问“谁能跳到我”，不如问“我能跳到哪里”。
当我们站在第i层，已知到达这里的最小步数是dp[i]，那么我们可以更新未来一段区间[i+1, i+L[i]]的最小步数为dp[i] + 1。但这依然涉及区间更新，处理起来比较麻烦。

让我们回到最本质的贪心思想结合 DP。既然每一步的代价都是 1，那么要使总步数最少，每一步都应该尽可能跳得远吗？不完全是。正确的逻辑是：在当前能到达的所有楼层中，选择那个能让我“下一步”跳得最远的楼层。

这其实可以转化为一个类似“跳跃游戏 II"的问题。我们可以维护两个变量：

1. current_end：当前这一步所能到达的最远边界。
2. farthest：在当前这一步的范围内，下一次能跳到的最远位置。

算法流程如下：

• 初始化steps = 0，current_end = 0，farthest = 0。
• 遍历楼层i从0到n-2（因为到了n-1就结束了）：
  • 更新farthest = max(farthest, i + L[i])。
  • 如果i到达了current_end，说明必须再坐一次电梯了：
    • steps += 1
    • current_end = farthest
    • 如果current_end >= n-1，可以直接返回steps。

这种写法将时间复杂度完美压缩到了O(n)O(n)O(n)，空间复杂度仅为O(1)O(1)O(1)（如果不算输入数组）。它避开了复杂的 DP 数组填充，利用了题目中“代价恒定”的特性，将 DP 状态压缩成了几个游标。

在实现时，需要注意边界条件：如果某一步的farthest没有超过current_end，说明无法继续前进，此时应判定为不可达（虽然题目隐含通常有解，但健壮的程序需考虑此情况）。这种O(n)O(n)O(n)的解法不仅能轻松应对百万级数据，也是面试中考察线性扫描能力的经典范例。

坦克消灭敌人：区间动态规划的智慧

第二个任务将场景切换到了战场。你有n辆坦克排成一队，每天只能从队列的头部或尾部取出一辆坦克投入战斗。第i天（从第 1 天开始计数）出战的坦克，其消灭敌人的数量等于该坦克的战斗力数值乘以天数i。随着战事加剧，天数越靠后， multiplier 越大。目标是安排出战顺序，使得n天后消灭的敌人总数最大。

为什么暴力搜索行不通

这道题乍一看像是一个贪心问题：是不是应该把战斗力弱的坦克先派出去，留强的到最后？或者反过来？
简单的贪心策略在这里往往会失效。例如，坦克序列为[1, 100, 2]。

• 如果第一天选最小的 1（头），剩[100, 2]；第二天选 2（尾），剩[100]；第三天 100。总分：1×1+2×2+100×3=3051\times1 + 2\times2 + 100\times3 = 3051×1+2×2+100×3=305。
• 如果第一天选 2（尾），剩[1, 100]；第二天选 1（头），剩[100]；第三天 100。总分：2×1+1×2+100×3=3042\times1 + 1\times2 + 100\times3 = 3042×1+1×2+100×3=304。
  看起来好像要把小的先送走。但如果序列是[10, 1, 10]呢？
• 先送 10（头）：10×1+1×2+10×3=4210\times1 + 1\times2 + 10\times3 = 4210×1+1×2+10×3=42。
• 先送 10（尾）：10×1+1×2+10×3=4210\times1 + 1\times2 + 10\times3 = 4210×1+1×2+10×3=42。
• 如果中间有个特别大的数，策略又会变化。

由于每一天的选择都会影响剩余序列的结构，进而影响后续所有天数的乘数分配，局部最优推不出全局最优。暴力递归枚举所有2n2^n2n种取法，在n稍大时（比如n=20）就会超时，而作业要求的n显然更大，因此必须使用动态规划。

区间 DP 的状态设计

这是一个典型的区间动态规划问题。我们关注的不是“第几天选哪辆车”，而是“对于剩下的这一段连续子序列，能获得的最大收益是多少”。

定义dp[i][j]表示：当只剩下原队列中下标从i到j的这部分坦克时（包含i和j），从当前天数开始直到结束，能获得的最大消灭敌人数。

假设当前剩下的坦克数量是len = j - i + 1。
原来的总天数是n，现在已经过去了n - len天，所以当前是第n - len + 1天。记当前天数为day。

对于区间[i, j]，我们有两种选择：

1. 选头部i：获得的收益是tanks[i] * day，加上剩余区间[i+1, j]的最优解。
   score1=tanks[i]×day+dp[i+1][j]score_1 = tanks[i] \times day + dp[i+1][j]score1​=tanks[i]×day+dp[i+1][j]
2. 选尾部j：获得的收益是tanks[j] * day，加上剩余区间[i, j-1]的最优解。
   score2=tanks[j]×day+dp[i][j−1]score_2 = tanks[j] \times day + dp[i][j-1]score2​=tanks[j]×day+dp[i][j−1]

状态转移方程即为：
dp[i][j]=max⁡(score1,score2)dp[i][j] = \max(score_1, score_2)dp[i][j]=max(score1​,score2​)

记忆化搜索与迭代实现

实现上有两种主流方式：自顶向下的记忆化搜索（Memoization）和自底向上的迭代填表。

记忆化搜索写法更符合人类直觉。编写一个递归函数solve(i, j)，内部检查memo[i][j]是否已计算。如果没有，则按上述方程递归调用solve(i+1, j)和solve(i, j-1)。这种方法代码简洁，且只会计算 reachable 的状态。但在 Python 等语言中，递归深度受限，若n较大（如几千），可能会触发栈溢出错误，需要手动设置递归深度限制或使用迭代法。

迭代填表则更加稳健。我们需要按照区间长度len从小到大进行循环：

• 外层循环：length从 1 到n。
• 内层循环：i从 0 到n - length，计算j = i + length - 1。
• 在循环体内计算day = n - length + 1，然后应用转移方程。

最终答案即为dp[0][n-1]。

关于空间复杂度，标准的二维 DP 需要O(n2)O(n^2)O(n2)的空间。作业提示中提到"low memory usage (e.g. O(n)) is preferred"。对于区间 DP，通常很难直接压缩到O(n)O(n)O(n)，因为dp[i][j]依赖于不同长度的子区间。但在某些特定变种或通过滚动数组技巧（如果依赖关系允许），或许能优化。不过，针对本题的标准解法，O(n2)O(n^2)O(n2)的空间在n为几千时通常是可接受的（几百万个整数约占几十 MB 内存）。如果n真的非常大，可能需要重新审视是否有贪心性质被遗漏，或者使用更高级的空间优化技巧，但在常规算法课语境下，写出正确的O(n2)O(n^2)O(n2)解法是核心目标。

对比暴力解法，DP 将指数级的时间复杂度降为了多项式级O(n2)O(n^2)O(n2)，这是质的飞跃。在本地测试时，可以构造一个n=1000的随机数组，暴力法可能跑几秒甚至几分钟，而 DP 版本应在毫秒级完成。

学术诚信与工程实践的红线

在深入探讨算法实现的同时，必须严肃对待 Computer Science 320SC 作业中强调的学术诚信（Academic Integrity）原则。这不仅是课程要求，更是程序员职业生涯的底线。

首先，严禁直接抄袭。无论是复制同学的代码，还是直接从 StackOverflow、GitHub 或各类 AI 工具中获取完整解决方案并稍作修改变量名提交，都属于严重的学术不端行为。现在的自动评测系统（如 MOSS）具备强大的代码指纹识别能力，能够轻易检测出结构相似性极高的代码，哪怕变量名被替换，控制流和逻辑结构的相似度也会暴露无遗。往年已有不少学生因此受到处罚，得不偿失。

其次，正确使用辅助工具。参考网上的思路、阅读相关的算法解析文章、甚至利用 AI 解释概念都是被鼓励的学习方式。关键在于“理解后的重构”。你需要自己动手将思路转化为代码，确保每一行逻辑都经过自己的大脑处理。如果你使用了外部资源，最好在注释中简要说明灵感来源，这体现了诚实的科研态度。

最后，本地验证的重要性。作业中提到，过度提交（超过 10 次）会被扣分。这倒逼我们在提交前必须进行充分的本地测试。不要依赖自动评分器来帮你找 Bug。

• 构造边界用例：测试n=1的情况，测试所有坦克战斗力相同的情况，测试单调递增或递减的序列。
• 小规模对拍：写一个暴力的递归版本（仅用于小数据），和一个优化的 DP 版本，在n=10或n=20的小规模数据上进行大量随机测试，对比两者输出是否一致。只有当小数据完全吻合，且大数据运行时间符合预期时，再考虑提交。

这种“本地充分测试 -> 少量提交验证”的工程习惯，远比盲目试错要高效得多，也是区分初级Coder和成熟工程师的重要标志。

结语

动态规划的魅力在于它将复杂的全局决策问题，拆解为一系列可管理的局部最优子问题。无论是电梯调度中对线性状态的极致压缩，还是坦克作战中区间思维的巧妙运用，核心都在于准确定义状态并找到正确的转移路径。

在实际的软件开发和算法面试中，我们遇到的往往不是原题，而是这些经典模型的变体。掌握这类问题的分析范式——从暴力枚举入手，识别重叠子问题，定义状态，推导方程，最后优化时空复杂度——才是学习算法的真正目的。希望通过对这两个案例的剖析，能让你在面对类似的 DP 难题时，多一份从容，少一份迷茫。记住，代码只是思想的载体，清晰的逻辑推导才是解决问题的钥匙。