1. 项目概述与核心思路拆解“跳格子3”这个题目乍一听像是某种小游戏但在华为OD机试的语境下它是一道典型的动态规划Dynamic Programming, DP算法题。这类题目考察的核心远不止是写出能跑通的代码更是对问题建模、状态定义、转移方程推导以及边界条件处理等综合能力的检验。我参加过也辅导过不少机试发现很多朋友一看到“动态规划”四个字就发怵其实只要拆解得当这类问题都有清晰的解决路径。这道题目的经典描述通常是有一个一维的格子序列每个格子有一个分数或代价。你从起点出发每次可以向前跳跃若干步跳跃规则是题目的核心约束比如每次最多跳k步或者有特定的跳跃消耗目标是到达终点或某个位置时获得的总分最大或总代价最小。 “跳格子3”这个命名暗示它可能是“跳格子”系列问题的变种或升级通常意味着状态定义或转移条件会更加复杂一层例如加入了“不能连续跳相同步数”、“跳跃消耗与格子属性相关”或者“有额外的状态如能量、冷却”等维度。解决这类问题的通用思路我习惯称之为“四步定乾坤”定义状态、确定初始值、推导转移方程、明确最终答案。对于“跳格子3”我们首先要根据题目描述虽然这里没有给出但我们可以基于常见模式进行合理推演确定多出来的那个“3”代表什么。一个非常常见的设定是你拥有3次“超级跳跃”的机会每次超级跳跃可以无视常规跳跃规则跳到任意更远的格子但使用超级跳跃后下一个常规跳跃会有惩罚或限制。这就需要我们在状态中额外记录一个维度已经使用过的超级跳跃次数。这样一来我们的解题框架就清晰了。2. 核心算法原理与状态设计动态规划的精髓在于“状态”。一个好的状态设计应该能唯一地描述在解决问题过程中的某个“局面”并且这个局面之后的决策只依赖于这个状态本身与如何到达这个状态的历史路径无关无后效性。对于基础的跳格子问题无超级跳跃状态可以非常简单设dp[i]表示跳到第i个格子时能获得的最大分数。那么转移方程就是dp[i] max(dp[i-k], dp[i-k1], ..., dp[i-1]) score[i]其中k是最大跳跃步数。这是最朴素的一维线性DP。而“跳格子3”引入的“3次机会”打破了这种简单的一维结构。我们必须将“已使用机会次数”纳入状态。因此一个合理的状态设计是dp[i][j]表示跳到第i个格子并且在这个过程中已经使用了j次超级跳跃时能获得的最大分数。其中i是格子索引从0或1开始j的取值范围是 0, 1, 2, 3。有了这个二维状态我们就需要思考两种动作常规跳跃和使用超级跳跃。常规跳跃从格子p跳到格子i需要满足常规跳跃约束例如1 i - p KK为常规最大步数。这个动作不会消耗超级跳跃次数。因此对于dp[i][j]它可以从所有满足跳跃条件的dp[p][j]转移而来。超级跳跃从任意格子pp i直接跳到格子i。这个动作会消耗1次超级跳跃机会。因此对于dp[i][j]它可以从所有dp[p][j-1]转移而来这里要求j 1。最终的转移方程需要综合这两种情况取最大值dp[i][j] max(常规跳跃来源最大值, 超级跳跃来源最大值) score[i]其中常规跳跃来源最大值 max(dp[p][j])对于所有满足i - K p i的p。超级跳跃来源最大值 max(dp[p][j-1])对于所有p i且j 1。这里就引出了第一个实操难点和优化点如果对每个dp[i][j]都去遍历所有p找最大值时间复杂度会高达 O(N^2 * 4)在数据量稍大时N上万很容易超时。因此我们必须对“取最大值”的过程进行优化。对于常规跳跃的max(dp[p][j])由于p的范围是一个长度为K的滑动窗口我们可以使用单调队列来优化将求窗口最大值的时间复杂度从 O(K) 降为 O(1)。这是解决此类“滑动窗口最值”问题的标准技巧。对于超级跳跃的max(dp[p][j-1])因为p的范围是从0到i-1我们可以在遍历i的过程中维护一个到当前位置为止的dp[p][j-1]的前缀最大值这样也能在 O(1) 时间内得到。注意状态设计是动态规划最核心也最灵活的一步。有些题目变种可能不是“使用次数”而是“剩余次数”即dp[i][j]表示跳到i格子还剩j次超级跳跃。这两种定义是等价的但在初始化起点拥有3次机会和转移方程使用跳跃时j减少上会有对称的差异。选择一种自己觉得最顺手的即可关键是保持逻辑一致。3. C实现详解与代码逐行解析理解了算法原理和状态设计后我们来看C实现。我会先给出一个清晰、模块化的代码框架然后逐部分解释。这里假设题目输入为格子数量n每个格子的分数数组scores长度为n常规跳跃最大步数K以及超级跳跃总次数M此处M3。目标是到达最后一个格子索引n-1时的最大分数。#include iostream #include vector #include deque #include algorithm #include climits using namespace std; long long solve(int n, vectorint scores, int K, int M) { // 1. 初始化DP数组用LLONG_MIN表示不可达状态 // dp[i][j]: 跳到第i个格子使用了j次超级跳跃的最大得分 vectorvectorlong long dp(n, vectorlong long(M 1, LLONG_MIN)); // 2. 初始化起点状态 // 站在起点0未使用超级跳跃得分为scores[0] dp[0][0] scores[0]; // 注意题目有时允许从起点直接使用超级跳跃这取决于规则。 // 如果允许那么 dp[0][1] 也可能被初始化为 scores[0]使用一次跳到原地通常不合理。 // 更常见的理解是超级跳跃是从一个格子跳到另一个格子所以起点状态只有dp[0][0]是有效的。 // 用于优化常规跳跃的单调队列数组每个使用次数j维护一个队列 vectordequeint monoQueues(M 1); // 用于优化超级跳跃的前缀最大值数组 // preMax[j] 记录对于当前固定的i所有p i的dp[p][j]的最大值 vectorlong long preMax(M 1, LLONG_MIN); // 初始化起点的前缀最大值 preMax[0] dp[0][0]; // 对于j0目前只有dp[0][0]是有效的 // 将起点0放入各个次数的单调队列虽然只有j0有效但统一操作 for (int j 0; j M; j) { if (dp[0][j] ! LLONG_MIN) { // 维护单调队列递减从队尾移除比当前dp值小的元素 while (!monoQueues[j].empty() dp[monoQueues[j].back()][j] dp[0][j]) { monoQueues[j].pop_back(); } monoQueues[j].push_back(0); } } // 3. 状态转移 for (int i 1; i n; i) { // 临时数组用于存储本轮计算出的所有dp[i][j] vectorlong long currentDp(M 1, LLONG_MIN); for (int j 0; j M; j) { long long bestFromNormal LLONG_MIN; long long bestFromSuper LLONG_MIN; // 3.1 从常规跳跃转移 if (!monoQueues[j].empty()) { // 单调队列队首即为窗口[i-K, i-1]内dp[p][j]的最大值 bestFromNormal dp[monoQueues[j].front()][j]; } // 3.2 从超级跳跃转移 (j 1) if (j 0 preMax[j - 1] ! LLONG_MIN) { bestFromSuper preMax[j - 1]; } // 3.3 综合两种转移方式取最优值 long long bestPrev max(bestFromNormal, bestFromSuper); if (bestPrev ! LLONG_MIN) { // 只有能从某个状态转移过来当前状态才有效 currentDp[j] bestPrev scores[i]; } // 3.4 更新用于超级跳跃优化的前缀最大值preMax[j] // 注意这里更新的是“旧”的dp[p][j]即i-1及之前的。 // 我们会在本轮所有j循环结束后用currentDp去更新dp数组和preMax。 } // 4. 更新dp数组并维护单调队列和前缀最大值 for (int j 0; j M; j) { dp[i][j] currentDp[j]; // 更新前缀最大值preMax[j] if (dp[i][j] ! LLONG_MIN) { preMax[j] max(preMax[j], dp[i][j]); } // 维护单调队列monoQueues[j] // 4.1 移除队首超出窗口范围(i-K)的元素 while (!monoQueues[j].empty() monoQueues[j].front() i - K 1) { // 注意窗口左边界 monoQueues[j].pop_front(); } // 4.2 将当前下标i加入队列前提是状态有效 if (dp[i][j] ! LLONG_MIN) { while (!monoQueues[j].empty() dp[monoQueues[j].back()][j] dp[i][j]) { monoQueues[j].pop_back(); } monoQueues[j].push_back(i); } } } // 5. 获取答案 // 最终目标是到达最后一个格子n-1可能使用了0到M次超级跳跃取最大值 long long ans LLONG_MIN; for (int j 0; j M; j) { ans max(ans, dp[n - 1][j]); } // 如果ans仍是LLONG_MIN说明终点不可达根据题目通常不会 return ans LLONG_MIN ? -1 : ans; // 根据题目要求返回可能直接返回ans } int main() { // 示例输入 int n 7; vectorint scores {1, 2, 3, -4, -2, 5, 1}; int K 3; // 常规跳跃最大步数 int M 2; // 超级跳跃次数这里假设是2次作为例子 long long result solve(n, scores, K, M); cout 最大得分: result endl; return 0; }代码关键点解析状态初始化使用LLONG_MIN表示不可达状态这是一个好习惯可以避免初始值0对求最大值操作的干扰。起点dp[0][0]初始化为scores[0]。单调队列优化我们为每个超级跳跃使用次数j维护了一个独立的单调队列monoQueues[j]。队列中存储的是格子索引保证其对应的dp[p][j]值从队首到队尾是递减的。这样队首元素就是当前滑动窗口内dp[p][j]的最大值。push_back时要弹出队尾所有值小于等于当前值的元素以维持递减性。pop_front时检查队首索引是否已经滑出窗口 i - K 1。这里的1需要根据你对“跳跃步数”的定义微调是严格小于K还是小于等于K。前缀最大值优化preMax[j]记录了在遍历到当前位置i时所有p i的dp[p][j]的最大值。这用于快速得到超级跳跃的转移来源最大值。在每计算完一个dp[i][j]后需要更新对应的preMax[j]。转移顺序在循环中我们先利用上一轮维护好的monoQueues和preMax计算出本格子所有j对应的currentDp。然后再用currentDp去更新dp数组并同时更新monoQueues和preMax为下一轮做准备。这个顺序不能乱否则会用到“未来”的信息。答案获取终点n-1可能对应不同的超级跳跃使用次数我们需要遍历j从0到M取dp[n-1][j]的最大值作为最终答案。实操心得在机试的紧张环境下很容易在窗口边界和下标处理上出错。我的建议是在纸上画一个简单的例子比如n5, K2手动模拟一下单调队列和前缀最大值的变化过程。把i、K、窗口左右边界的关系写清楚可以避免很多调试时间。另外对于LLONG_MIN的判断要格外小心任何涉及它的运算尤其是加法都可能溢出所以要先判断来源状态是否有效 (! LLONG_MIN)再进行加分操作。4. 不同场景下的变种与应对策略“跳格子”问题是一个母题围绕它可以衍生出无数变种。除了我们刚才实现的“有限次超级跳跃”在OD机试或其他算法题库中你还可能遇到以下几种典型变种。掌握核心的DP状态设计思想后这些变种无非是状态维度的增减或转移条件的修改。4.1 变种一带负权分数与不可达格子这是最常见的变种之一。某些格子分数为负或者某些格子是“陷阱”根本不能站上去分数为负无穷。我们的解法已经通过LLONG_MIN处理了不可达状态。关键在于初始化和转移判断。如果起点或终点可能是陷阱需要在初始化或最终答案判断时处理。在转移时只有来源状态有效! LLONG_MIN且目标格子有效分数不为负无穷时才能进行转移。在我们的代码框架中这体现在if (bestPrev ! LLONG_MIN)这一行。4.2 变种二跳跃消耗与格子属性绑定例如每个格子有一个“颜色”或“类型”从红色格子跳到蓝色格子消耗1点能量同色跳跃不消耗。此时我们的状态可能需要增加一个维度来表示“当前剩余能量”或者将“消耗”直接体现在状态值得分的减少上。如果能量是有限的那么状态就变成了三维dp[i][j][e]分别表示位置、已用超级跳跃次数、剩余能量。转移方程需要根据跳跃前后的格子类型来调整e的变化。这会显著增加时间和空间复杂度需要仔细评估数据范围。4.3 变种三求方案数或具体路径有时题目不仅要求最大得分还要求有多少种方式能获得这个最大得分或者要求输出得分最高的具体跳跃路径。求方案数需要另开一个与dp数组结构相同的ways数组。ways[i][j]表示达到dp[i][j]这个最大得分的方案数。在转移时如果从某个来源p转移到i能得到一个新的更大的dp[i][j]则ways[i][j] ways[p][对应j]如果得到的是相等的dp[i][j]则ways[i][j] ways[p][对应j]。最后将所有能取得最大得分的终态ways[n-1][j]累加起来。求具体路径这比求方案数更复杂。需要用一个pre[i][j]数组来记录状态(i, j)是由哪个前驱状态(p, prev_j)转移而来的同时记录是常规跳跃还是超级跳跃。在DP结束后从取得最大得分的终态反向回溯即可得到路径。注意如果最大得分对应多个前驱通常题目会要求输出字典序最小或类似的路径这就需要我们在转移时当得分相同时按照路径的字典序规则来优先选择某个前驱。4.4 变种四起点终点不固定/环形格子例如可以从任意格子开始在任意格子结束。或者格子是环形的即最后一个格子与第一个格子相连。对于起点不固定通常的解法是初始化所有格子为起点dp[i][0] scores[i]然后进行DP。对于环形一个常用技巧是“破环成链”即将原数组复制一份接在后面然后在新数组上做DP但限制跳跃长度和总路径长度不超过原数组长度n。应对策略总结面对变种不要慌。核心永远是那“四步”。先仔细阅读题目确定影响决策的关键因素如剩余跳跃次数、能量、颜色、是否连续等这些因素就是你需要添加到状态中的维度。然后思考在状态之间这些维度如何随着“跳跃”这个动作发生变化从而写出转移方程。最后考虑初始化和边界条件。在机试中如果时间有限优先保证基础版本如我们上面实现的的正确性和效率变种部分可以写下思路有时也能获得部分分数。5. 机试实战技巧与调试心得在华为OD或其他公司的在线机试环境中把代码写出来只是第一步能一次性通过所有测试用例才是目标。结合“跳格子3”这类动态规划题目我分享几个实战中救过我很多次的技巧。5.1 数据范围与类型选择这是第一道关卡。题目中给出的分数范围是多少如果每个分数是-10^4 ~ 10^4n最大为10^5那么总分的理论范围就在-10^9 ~ 10^9之间这还在int的范围内约±21亿。但是如果你用了int类型的LLONG_MIN做初始化或者中间计算过程用了int导致溢出就会出错。更稳妥的做法是仔细阅读题目给出的数据范围。无脑使用long long来定义DP数组和中间变量。在大多数机试平台long long的开销是可以接受的它能避免绝大多数溢出问题。就像我们示例代码中做的那样。5.2 测试用例设计不要只相信题目给的样例。样例往往很简单覆盖不到边界情况。自己必须设计几个关键测试用例极小用例n1。只有一个格子答案就是它的分数。检查你的初始化逻辑。无法到达终点的用例比如K0不允许常规跳跃而超级跳跃次数M0或者所有中间格子都是“陷阱”。你的程序应该能正确处理返回一个特定的无效值如-1而不是崩溃或输出错误结果。全负分数用例所有格子分数都是负数。你的算法应该能正确找到“最大”的负数即绝对值最小的损失而不是返回0或初始值。超级跳跃次数用不完的用例M很大但可能用不到。确保你的状态转移和最终答案遍历能覆盖j从0到M的所有情况。常规跳跃窗口为1的用例K1。这相当于只能走一步可以用来检验单调队列在窗口大小为1时的边界处理。5.3 调试与输出中间状态在本地IDE调试时最有效的方法就是“打印DP表”。对于中等规模如n10的用例将整个dp数组打印出来与手动计算的结果对比。你可以写一个简单的暴力DP不加优化用于验证正确性来生成对照表。// 简单的暴力DP验证函数 (O(n^2 * M)仅用于小数据验证) long long bruteForce(int n, vectorint scores, int K, int M) { vectorvectorlong long dp(n, vectorlong long(M1, LLONG_MIN)); dp[0][0] scores[0]; for (int i 1; i n; i) { for (int j 0; j M; j) { // 常规跳跃 for (int p max(0, i-K); p i; p) { if (dp[p][j] ! LLONG_MIN) { dp[i][j] max(dp[i][j], dp[p][j] scores[i]); } } // 超级跳跃 if (j 0) { for (int p 0; p i; p) { if (dp[p][j-1] ! LLONG_MIN) { dp[i][j] max(dp[i][j], dp[p][j-1] scores[i]); } } } } } // ... 取最大值返回 }用这个暴力算法跑通小数据确保你的优化算法单调队列前缀最大值得出的dp表与之一致。这是验证算法正确性的黄金标准。5.4 常见“坑点”与排查清单初始化错误起点状态设错。比如dp[0][0]是否等于scores[0]dp[0][1]是否应该初始化通常不应该除非规则特殊。下标越界在单调队列中判断窗口左边界i - K时要注意是i - K还是i - K 1这取决于你对“跳跃步数”的定义从p跳到i步数是i-p要求1 i-p K所以p i-K且p i。在代码中我们判断队首是否 i - K 1来弹出是因为我们希望窗口包含i-K这个索引。整数溢出如前所述坚持用long long。不可达状态处理所有涉及dp值运算的地方都要先判断其是否为LLONG_MIN不可达。特别是更新preMax和向单调队列中添加元素时。答案遍历不全最终答案要遍历所有j(0..M)而不仅仅是dp[n-1][M]。可能最优解并没有用完所有超级跳跃。5.5 时间与空间复杂度分析时间复杂度我们优化后的算法外层循环i从1到n-1内层循环j从0到M。内层循环中的单调队列操作和前缀最大值更新都是 O(1)。因此总时间复杂度为O(n * M)。其中M是超级跳跃次数通常是个很小的常数比如3所以可以近似看作 O(n)。空间复杂度DP数组是n * (M1)单调队列数组存储的是索引总体也是 O(n * M)。在n很大时如10^5如果M也很大空间可能成为问题。这时可以观察状态转移是否只依赖于前一行或前几行从而进行滚动数组优化将空间降至 O(M) 或 O(K * M)。对于本题由于我们使用了单调队列队列中需要保存索引以判断窗口滚动优化会稍微复杂但如果M很小通常n * (M1)的空间是可以接受的10^5 * 4 ≈ 400k个long long约3MB。最后在机试环境中如果实在想不出优化方案比如单调队列先实现一个正确但慢的暴力DPO(n^2)提交有时也能通过一部分测试用例拿到分数。但对于“跳格子3”这种明显卡时间的数据范围掌握单调队列这类经典优化是必不可少的。平时多积累几种常见的DP优化技巧单调队列、斜率优化、四边形不等式等在考场上才能游刃有余。
华为OD机试“跳格子3”动态规划详解：状态设计与单调队列优化
1. 项目概述与核心思路拆解“跳格子3”这个题目乍一听像是某种小游戏但在华为OD机试的语境下它是一道典型的动态规划Dynamic Programming, DP算法题。这类题目考察的核心远不止是写出能跑通的代码更是对问题建模、状态定义、转移方程推导以及边界条件处理等综合能力的检验。我参加过也辅导过不少机试发现很多朋友一看到“动态规划”四个字就发怵其实只要拆解得当这类问题都有清晰的解决路径。这道题目的经典描述通常是有一个一维的格子序列每个格子有一个分数或代价。你从起点出发每次可以向前跳跃若干步跳跃规则是题目的核心约束比如每次最多跳k步或者有特定的跳跃消耗目标是到达终点或某个位置时获得的总分最大或总代价最小。 “跳格子3”这个命名暗示它可能是“跳格子”系列问题的变种或升级通常意味着状态定义或转移条件会更加复杂一层例如加入了“不能连续跳相同步数”、“跳跃消耗与格子属性相关”或者“有额外的状态如能量、冷却”等维度。解决这类问题的通用思路我习惯称之为“四步定乾坤”定义状态、确定初始值、推导转移方程、明确最终答案。对于“跳格子3”我们首先要根据题目描述虽然这里没有给出但我们可以基于常见模式进行合理推演确定多出来的那个“3”代表什么。一个非常常见的设定是你拥有3次“超级跳跃”的机会每次超级跳跃可以无视常规跳跃规则跳到任意更远的格子但使用超级跳跃后下一个常规跳跃会有惩罚或限制。这就需要我们在状态中额外记录一个维度已经使用过的超级跳跃次数。这样一来我们的解题框架就清晰了。2. 核心算法原理与状态设计动态规划的精髓在于“状态”。一个好的状态设计应该能唯一地描述在解决问题过程中的某个“局面”并且这个局面之后的决策只依赖于这个状态本身与如何到达这个状态的历史路径无关无后效性。对于基础的跳格子问题无超级跳跃状态可以非常简单设dp[i]表示跳到第i个格子时能获得的最大分数。那么转移方程就是dp[i] max(dp[i-k], dp[i-k1], ..., dp[i-1]) score[i]其中k是最大跳跃步数。这是最朴素的一维线性DP。而“跳格子3”引入的“3次机会”打破了这种简单的一维结构。我们必须将“已使用机会次数”纳入状态。因此一个合理的状态设计是dp[i][j]表示跳到第i个格子并且在这个过程中已经使用了j次超级跳跃时能获得的最大分数。其中i是格子索引从0或1开始j的取值范围是 0, 1, 2, 3。有了这个二维状态我们就需要思考两种动作常规跳跃和使用超级跳跃。常规跳跃从格子p跳到格子i需要满足常规跳跃约束例如1 i - p KK为常规最大步数。这个动作不会消耗超级跳跃次数。因此对于dp[i][j]它可以从所有满足跳跃条件的dp[p][j]转移而来。超级跳跃从任意格子pp i直接跳到格子i。这个动作会消耗1次超级跳跃机会。因此对于dp[i][j]它可以从所有dp[p][j-1]转移而来这里要求j 1。最终的转移方程需要综合这两种情况取最大值dp[i][j] max(常规跳跃来源最大值, 超级跳跃来源最大值) score[i]其中常规跳跃来源最大值 max(dp[p][j])对于所有满足i - K p i的p。超级跳跃来源最大值 max(dp[p][j-1])对于所有p i且j 1。这里就引出了第一个实操难点和优化点如果对每个dp[i][j]都去遍历所有p找最大值时间复杂度会高达 O(N^2 * 4)在数据量稍大时N上万很容易超时。因此我们必须对“取最大值”的过程进行优化。对于常规跳跃的max(dp[p][j])由于p的范围是一个长度为K的滑动窗口我们可以使用单调队列来优化将求窗口最大值的时间复杂度从 O(K) 降为 O(1)。这是解决此类“滑动窗口最值”问题的标准技巧。对于超级跳跃的max(dp[p][j-1])因为p的范围是从0到i-1我们可以在遍历i的过程中维护一个到当前位置为止的dp[p][j-1]的前缀最大值这样也能在 O(1) 时间内得到。注意状态设计是动态规划最核心也最灵活的一步。有些题目变种可能不是“使用次数”而是“剩余次数”即dp[i][j]表示跳到i格子还剩j次超级跳跃。这两种定义是等价的但在初始化起点拥有3次机会和转移方程使用跳跃时j减少上会有对称的差异。选择一种自己觉得最顺手的即可关键是保持逻辑一致。3. C实现详解与代码逐行解析理解了算法原理和状态设计后我们来看C实现。我会先给出一个清晰、模块化的代码框架然后逐部分解释。这里假设题目输入为格子数量n每个格子的分数数组scores长度为n常规跳跃最大步数K以及超级跳跃总次数M此处M3。目标是到达最后一个格子索引n-1时的最大分数。#include iostream #include vector #include deque #include algorithm #include climits using namespace std; long long solve(int n, vectorint scores, int K, int M) { // 1. 初始化DP数组用LLONG_MIN表示不可达状态 // dp[i][j]: 跳到第i个格子使用了j次超级跳跃的最大得分 vectorvectorlong long dp(n, vectorlong long(M 1, LLONG_MIN)); // 2. 初始化起点状态 // 站在起点0未使用超级跳跃得分为scores[0] dp[0][0] scores[0]; // 注意题目有时允许从起点直接使用超级跳跃这取决于规则。 // 如果允许那么 dp[0][1] 也可能被初始化为 scores[0]使用一次跳到原地通常不合理。 // 更常见的理解是超级跳跃是从一个格子跳到另一个格子所以起点状态只有dp[0][0]是有效的。 // 用于优化常规跳跃的单调队列数组每个使用次数j维护一个队列 vectordequeint monoQueues(M 1); // 用于优化超级跳跃的前缀最大值数组 // preMax[j] 记录对于当前固定的i所有p i的dp[p][j]的最大值 vectorlong long preMax(M 1, LLONG_MIN); // 初始化起点的前缀最大值 preMax[0] dp[0][0]; // 对于j0目前只有dp[0][0]是有效的 // 将起点0放入各个次数的单调队列虽然只有j0有效但统一操作 for (int j 0; j M; j) { if (dp[0][j] ! LLONG_MIN) { // 维护单调队列递减从队尾移除比当前dp值小的元素 while (!monoQueues[j].empty() dp[monoQueues[j].back()][j] dp[0][j]) { monoQueues[j].pop_back(); } monoQueues[j].push_back(0); } } // 3. 状态转移 for (int i 1; i n; i) { // 临时数组用于存储本轮计算出的所有dp[i][j] vectorlong long currentDp(M 1, LLONG_MIN); for (int j 0; j M; j) { long long bestFromNormal LLONG_MIN; long long bestFromSuper LLONG_MIN; // 3.1 从常规跳跃转移 if (!monoQueues[j].empty()) { // 单调队列队首即为窗口[i-K, i-1]内dp[p][j]的最大值 bestFromNormal dp[monoQueues[j].front()][j]; } // 3.2 从超级跳跃转移 (j 1) if (j 0 preMax[j - 1] ! LLONG_MIN) { bestFromSuper preMax[j - 1]; } // 3.3 综合两种转移方式取最优值 long long bestPrev max(bestFromNormal, bestFromSuper); if (bestPrev ! LLONG_MIN) { // 只有能从某个状态转移过来当前状态才有效 currentDp[j] bestPrev scores[i]; } // 3.4 更新用于超级跳跃优化的前缀最大值preMax[j] // 注意这里更新的是“旧”的dp[p][j]即i-1及之前的。 // 我们会在本轮所有j循环结束后用currentDp去更新dp数组和preMax。 } // 4. 更新dp数组并维护单调队列和前缀最大值 for (int j 0; j M; j) { dp[i][j] currentDp[j]; // 更新前缀最大值preMax[j] if (dp[i][j] ! LLONG_MIN) { preMax[j] max(preMax[j], dp[i][j]); } // 维护单调队列monoQueues[j] // 4.1 移除队首超出窗口范围(i-K)的元素 while (!monoQueues[j].empty() monoQueues[j].front() i - K 1) { // 注意窗口左边界 monoQueues[j].pop_front(); } // 4.2 将当前下标i加入队列前提是状态有效 if (dp[i][j] ! LLONG_MIN) { while (!monoQueues[j].empty() dp[monoQueues[j].back()][j] dp[i][j]) { monoQueues[j].pop_back(); } monoQueues[j].push_back(i); } } } // 5. 获取答案 // 最终目标是到达最后一个格子n-1可能使用了0到M次超级跳跃取最大值 long long ans LLONG_MIN; for (int j 0; j M; j) { ans max(ans, dp[n - 1][j]); } // 如果ans仍是LLONG_MIN说明终点不可达根据题目通常不会 return ans LLONG_MIN ? -1 : ans; // 根据题目要求返回可能直接返回ans } int main() { // 示例输入 int n 7; vectorint scores {1, 2, 3, -4, -2, 5, 1}; int K 3; // 常规跳跃最大步数 int M 2; // 超级跳跃次数这里假设是2次作为例子 long long result solve(n, scores, K, M); cout 最大得分: result endl; return 0; }代码关键点解析状态初始化使用LLONG_MIN表示不可达状态这是一个好习惯可以避免初始值0对求最大值操作的干扰。起点dp[0][0]初始化为scores[0]。单调队列优化我们为每个超级跳跃使用次数j维护了一个独立的单调队列monoQueues[j]。队列中存储的是格子索引保证其对应的dp[p][j]值从队首到队尾是递减的。这样队首元素就是当前滑动窗口内dp[p][j]的最大值。push_back时要弹出队尾所有值小于等于当前值的元素以维持递减性。pop_front时检查队首索引是否已经滑出窗口 i - K 1。这里的1需要根据你对“跳跃步数”的定义微调是严格小于K还是小于等于K。前缀最大值优化preMax[j]记录了在遍历到当前位置i时所有p i的dp[p][j]的最大值。这用于快速得到超级跳跃的转移来源最大值。在每计算完一个dp[i][j]后需要更新对应的preMax[j]。转移顺序在循环中我们先利用上一轮维护好的monoQueues和preMax计算出本格子所有j对应的currentDp。然后再用currentDp去更新dp数组并同时更新monoQueues和preMax为下一轮做准备。这个顺序不能乱否则会用到“未来”的信息。答案获取终点n-1可能对应不同的超级跳跃使用次数我们需要遍历j从0到M取dp[n-1][j]的最大值作为最终答案。实操心得在机试的紧张环境下很容易在窗口边界和下标处理上出错。我的建议是在纸上画一个简单的例子比如n5, K2手动模拟一下单调队列和前缀最大值的变化过程。把i、K、窗口左右边界的关系写清楚可以避免很多调试时间。另外对于LLONG_MIN的判断要格外小心任何涉及它的运算尤其是加法都可能溢出所以要先判断来源状态是否有效 (! LLONG_MIN)再进行加分操作。4. 不同场景下的变种与应对策略“跳格子”问题是一个母题围绕它可以衍生出无数变种。除了我们刚才实现的“有限次超级跳跃”在OD机试或其他算法题库中你还可能遇到以下几种典型变种。掌握核心的DP状态设计思想后这些变种无非是状态维度的增减或转移条件的修改。4.1 变种一带负权分数与不可达格子这是最常见的变种之一。某些格子分数为负或者某些格子是“陷阱”根本不能站上去分数为负无穷。我们的解法已经通过LLONG_MIN处理了不可达状态。关键在于初始化和转移判断。如果起点或终点可能是陷阱需要在初始化或最终答案判断时处理。在转移时只有来源状态有效! LLONG_MIN且目标格子有效分数不为负无穷时才能进行转移。在我们的代码框架中这体现在if (bestPrev ! LLONG_MIN)这一行。4.2 变种二跳跃消耗与格子属性绑定例如每个格子有一个“颜色”或“类型”从红色格子跳到蓝色格子消耗1点能量同色跳跃不消耗。此时我们的状态可能需要增加一个维度来表示“当前剩余能量”或者将“消耗”直接体现在状态值得分的减少上。如果能量是有限的那么状态就变成了三维dp[i][j][e]分别表示位置、已用超级跳跃次数、剩余能量。转移方程需要根据跳跃前后的格子类型来调整e的变化。这会显著增加时间和空间复杂度需要仔细评估数据范围。4.3 变种三求方案数或具体路径有时题目不仅要求最大得分还要求有多少种方式能获得这个最大得分或者要求输出得分最高的具体跳跃路径。求方案数需要另开一个与dp数组结构相同的ways数组。ways[i][j]表示达到dp[i][j]这个最大得分的方案数。在转移时如果从某个来源p转移到i能得到一个新的更大的dp[i][j]则ways[i][j] ways[p][对应j]如果得到的是相等的dp[i][j]则ways[i][j] ways[p][对应j]。最后将所有能取得最大得分的终态ways[n-1][j]累加起来。求具体路径这比求方案数更复杂。需要用一个pre[i][j]数组来记录状态(i, j)是由哪个前驱状态(p, prev_j)转移而来的同时记录是常规跳跃还是超级跳跃。在DP结束后从取得最大得分的终态反向回溯即可得到路径。注意如果最大得分对应多个前驱通常题目会要求输出字典序最小或类似的路径这就需要我们在转移时当得分相同时按照路径的字典序规则来优先选择某个前驱。4.4 变种四起点终点不固定/环形格子例如可以从任意格子开始在任意格子结束。或者格子是环形的即最后一个格子与第一个格子相连。对于起点不固定通常的解法是初始化所有格子为起点dp[i][0] scores[i]然后进行DP。对于环形一个常用技巧是“破环成链”即将原数组复制一份接在后面然后在新数组上做DP但限制跳跃长度和总路径长度不超过原数组长度n。应对策略总结面对变种不要慌。核心永远是那“四步”。先仔细阅读题目确定影响决策的关键因素如剩余跳跃次数、能量、颜色、是否连续等这些因素就是你需要添加到状态中的维度。然后思考在状态之间这些维度如何随着“跳跃”这个动作发生变化从而写出转移方程。最后考虑初始化和边界条件。在机试中如果时间有限优先保证基础版本如我们上面实现的的正确性和效率变种部分可以写下思路有时也能获得部分分数。5. 机试实战技巧与调试心得在华为OD或其他公司的在线机试环境中把代码写出来只是第一步能一次性通过所有测试用例才是目标。结合“跳格子3”这类动态规划题目我分享几个实战中救过我很多次的技巧。5.1 数据范围与类型选择这是第一道关卡。题目中给出的分数范围是多少如果每个分数是-10^4 ~ 10^4n最大为10^5那么总分的理论范围就在-10^9 ~ 10^9之间这还在int的范围内约±21亿。但是如果你用了int类型的LLONG_MIN做初始化或者中间计算过程用了int导致溢出就会出错。更稳妥的做法是仔细阅读题目给出的数据范围。无脑使用long long来定义DP数组和中间变量。在大多数机试平台long long的开销是可以接受的它能避免绝大多数溢出问题。就像我们示例代码中做的那样。5.2 测试用例设计不要只相信题目给的样例。样例往往很简单覆盖不到边界情况。自己必须设计几个关键测试用例极小用例n1。只有一个格子答案就是它的分数。检查你的初始化逻辑。无法到达终点的用例比如K0不允许常规跳跃而超级跳跃次数M0或者所有中间格子都是“陷阱”。你的程序应该能正确处理返回一个特定的无效值如-1而不是崩溃或输出错误结果。全负分数用例所有格子分数都是负数。你的算法应该能正确找到“最大”的负数即绝对值最小的损失而不是返回0或初始值。超级跳跃次数用不完的用例M很大但可能用不到。确保你的状态转移和最终答案遍历能覆盖j从0到M的所有情况。常规跳跃窗口为1的用例K1。这相当于只能走一步可以用来检验单调队列在窗口大小为1时的边界处理。5.3 调试与输出中间状态在本地IDE调试时最有效的方法就是“打印DP表”。对于中等规模如n10的用例将整个dp数组打印出来与手动计算的结果对比。你可以写一个简单的暴力DP不加优化用于验证正确性来生成对照表。// 简单的暴力DP验证函数 (O(n^2 * M)仅用于小数据验证) long long bruteForce(int n, vectorint scores, int K, int M) { vectorvectorlong long dp(n, vectorlong long(M1, LLONG_MIN)); dp[0][0] scores[0]; for (int i 1; i n; i) { for (int j 0; j M; j) { // 常规跳跃 for (int p max(0, i-K); p i; p) { if (dp[p][j] ! LLONG_MIN) { dp[i][j] max(dp[i][j], dp[p][j] scores[i]); } } // 超级跳跃 if (j 0) { for (int p 0; p i; p) { if (dp[p][j-1] ! LLONG_MIN) { dp[i][j] max(dp[i][j], dp[p][j-1] scores[i]); } } } } } // ... 取最大值返回 }用这个暴力算法跑通小数据确保你的优化算法单调队列前缀最大值得出的dp表与之一致。这是验证算法正确性的黄金标准。5.4 常见“坑点”与排查清单初始化错误起点状态设错。比如dp[0][0]是否等于scores[0]dp[0][1]是否应该初始化通常不应该除非规则特殊。下标越界在单调队列中判断窗口左边界i - K时要注意是i - K还是i - K 1这取决于你对“跳跃步数”的定义从p跳到i步数是i-p要求1 i-p K所以p i-K且p i。在代码中我们判断队首是否 i - K 1来弹出是因为我们希望窗口包含i-K这个索引。整数溢出如前所述坚持用long long。不可达状态处理所有涉及dp值运算的地方都要先判断其是否为LLONG_MIN不可达。特别是更新preMax和向单调队列中添加元素时。答案遍历不全最终答案要遍历所有j(0..M)而不仅仅是dp[n-1][M]。可能最优解并没有用完所有超级跳跃。5.5 时间与空间复杂度分析时间复杂度我们优化后的算法外层循环i从1到n-1内层循环j从0到M。内层循环中的单调队列操作和前缀最大值更新都是 O(1)。因此总时间复杂度为O(n * M)。其中M是超级跳跃次数通常是个很小的常数比如3所以可以近似看作 O(n)。空间复杂度DP数组是n * (M1)单调队列数组存储的是索引总体也是 O(n * M)。在n很大时如10^5如果M也很大空间可能成为问题。这时可以观察状态转移是否只依赖于前一行或前几行从而进行滚动数组优化将空间降至 O(M) 或 O(K * M)。对于本题由于我们使用了单调队列队列中需要保存索引以判断窗口滚动优化会稍微复杂但如果M很小通常n * (M1)的空间是可以接受的10^5 * 4 ≈ 400k个long long约3MB。最后在机试环境中如果实在想不出优化方案比如单调队列先实现一个正确但慢的暴力DPO(n^2)提交有时也能通过一部分测试用例拿到分数。但对于“跳格子3”这种明显卡时间的数据范围掌握单调队列这类经典优化是必不可少的。平时多积累几种常见的DP优化技巧单调队列、斜率优化、四边形不等式等在考场上才能游刃有余。
