1. 项目概述从“蓝跳跳”到动态规划的实战拆解最近在复盘蓝桥杯的历年国赛真题第十一届的压轴题“蓝跳跳”给我留下了挺深的印象。这题初看像是个简单的模拟或者搜索但数据规模一上来直接暴力就会超时核心考点其实是动态规划结合循环数组优化。很多同学卡在这里要么是状态转移没想清楚要么是内存超限。今天我就结合这道题把动态规划的思路从头到尾捋一遍并重点讲讲如何用循环数组把空间复杂度从 O(N) 降到 O(K)这在算法竞赛里是个非常实用的技巧。无论你是正在备赛蓝桥杯还是想巩固动态规划这篇文章都能给你提供一套清晰的解题框架和避坑指南。简单描述下题意有一个长度为 L 的台阶编号1到L一个机器人“蓝跳跳”从第0格开始每次可以跳跃1到K步。但是有一个特殊限制不能连续两次跳跃都超过 p 步p K。问这个机器人从第0格恰好跳到第L格有多少种不同的跳跃方案。结果可能很大需要对一个给定的常数 M 取模。L 可以非常大比如 10^18K 一般不超过 10^5。这个数据范围直接宣告了任何与 L 成正比的算法都会超时必须找到与 L 无关的递推方法。2. 核心思路解析状态定义与转移方程面对这种计数问题而且有明显的步骤限制跳跃长度、连续跳跃约束动态规划几乎是第一选择。关键在于如何定义状态以及如何写出高效且正确的转移方程。2.1 状态定义与初步分析最直观的想法是定义dp[i]为跳到第 i 个台阶的方案总数。那么要跳到 i上一步可能从 i-1, i-2, ..., i-K 这些位置跳过来前提是这些位置大于等于0。转移方程似乎是dp[i] dp[i-1] dp[i-2] ... dp[i-K]但这忽略了一个至关重要的约束不能连续两次跳跃都超过 p 步。这意味着当前这一步的跳跃长度和上一步的跳跃长度是有关联的。我们之前的状态dp[i]只记录了“跳到 i 的方案数”却丢失了“最后一步是怎么跳过来的”这个关键信息。没有这个信息我们就无法判断当前这一步能否跳某个长度。所以状态必须包含“最后一步的跳跃长度”这个维度。我们重新定义状态dp[i][j]: 表示跳到第 i 个台阶且最后一步跳跃长度恰好为 j的方案数。其中1 j K。这样一来最终答案就是跳到第 L 格的所有可能最后一步的方案数之和即sum(dp[L][j]) for j in 1..K。2.2 转移方程的推导现在考虑dp[i][j]怎么来。要跳到 i 且最后一步是 j那么上一步一定在i-j的位置假设i-j 0。并且上一步在i-j的位置时的最后一步跳跃长度不能是 p的我们记为大跳因为题目限制不能连续两次大跳。因此我们需要分情况讨论如果当前步j p这是一次小跳那么上一步可以是任意长度的跳跃小跳或大跳都行因为没有连续大跳的限制。所以dp[i][j]可以从所有dp[i-j][t](1 t K) 转移过来。如果当前步j p这是一次大跳那么上一步必须是一次小跳即上一步的跳跃长度t p。所以dp[i][j]只能从dp[i-j][t](1 t p) 转移过来。用公式表示就是 对于i j若j p:dp[i][j] sum(dp[i-j][t])for t 1 to K若j p:dp[i][j] sum(dp[i-j][t])for t 1 to p这里sum(dp[i-j][t])就是跳到i-j位置的所有方案数我们记这个值为total[i-j]。而sum(dp[i-j][t]) for t1 to p是跳到i-j位置且最后一步为小跳的方案数我们记这个值为small[i-j]。那么方程可以简化为dp[i][j] total[i-j]当j pdp[i][j] small[i-j]当j p注意这里有一个边界条件当i j时意味着从起点0直接跳到 i这本身就是一种方案。在我们的状态定义下这对应于dp[i][i]当i K。更严谨的处理是初始化一个虚拟的dp[0][*]或者直接在计算时判断i-j 0时total[0] 1small[0] 1因为从起点开始可以认为“上一次跳跃”是虚拟的视为满足条件。通常我们设置dp[0][0]1或total[0]1作为起点。2.3 复杂度分析与优化方向如果我们直接开一个二维数组dp[L1][K1]空间复杂度是 O(LK)时间复杂度也是 O(LK)因为每个dp[i][j]都需要计算。当 L 高达 10^18 时这完全不可行。观察转移方程dp[i][j]只依赖于i-j位置的两个聚合值total[i-j]和small[i-j]。而i-j比i小。更重要的是total[x]和small[x]本身可以通过之前计算出的dp[x][*]求和得到。这引导我们想到两个优化时间优化我们不需要对每个 j 都重新求和。我们可以维护total[i]和small[i]两个数组它们满足total[i] sum(dp[i][j]) for j1..Ksmall[i] sum(dp[i][j]) for j1..p当我们计算完所有dp[i][j]后可以立即更新total[i]和small[i]供后面的i i使用。空间优化关键dp[i][j]只依赖于dp[i-j][*]。i-j与i的差最大为 K。也就是说要计算dp[i]我们只需要最近 K 行的dp值即dp[i-K]到dp[i-1]。因此我们完全不需要存储整个 L 行的dp值只需要一个大小为K1的循环数组或者说滑动窗口来维护最近 K 行的total和small值即可。这就是循环数组优化能将空间复杂度从 O(L) 降为 O(K)。3. 算法实现详解循环数组与动态规划的结合理解了思路我们来看具体实现。我们将实现分为几个关键步骤初始化、主循环递推、循环数组的下标管理以及取模操作。3.1 数据结构定义与初始化我们不再需要显式的二维dp数组。我们只需要total[i]: 跳到第 i 格的总方案数。small[i]: 跳到第 i 格且最后一步是小跳长度p的方案数。由于我们只需要最近 K 个total和small的值我们用两个长度至少为K1的数组或Java中的long[]来作为循环缓冲区记为total和small。数组下标idx对应实际的台阶编号i对K1取模。初始化定义total[0] 1。这表示跳到第0格起点有1种方案不跳。定义small[0] 1。起点也视为满足“最后一步是小跳”的条件虚拟满足。对于i从 1 到 K我们需要计算dp[i][j]但这里我们隐式计算直接累加到total[i]和small[i]。根据之前的公式对于长度j(1 j i)如果j p则dp[i][j] total[i-j]如果j p则dp[i][j] small[i-j]注意当j i时从0无法一步跳过来贡献为0。因此我们可以用循环计算total[i]和small[i]long[] total new long[K1]; // 循环数组 long[] small new long[K1]; total[0] 1; small[0] 1; for (int i 1; i K; i) { long sumTotal 0; long sumSmall 0; // 最后一步跳跃长度j for (int j 1; j K; j) { if (j i) break; // 跳不到 int prev i - j; // 上一步的位置 if (j p) { // 当前是小跳上一步任意 sumTotal (sumTotal total[prev % (K1)]) % MOD; sumSmall (sumSmall total[prev % (K1)]) % MOD; // 注意当前步是小跳所以这个方案要计入small[i] } else { // 当前是大跳上一步必须是小跳 sumTotal (sumTotal small[prev % (K1)]) % MOD; // 当前是大跳这个方案不计入small[i] } } total[i % (K1)] sumTotal; small[i % (K1)] sumSmall; }这里有一个关键点small[i]的定义是“跳到 i 且最后一步是小跳的方案数”。所以在内层循环中只有当j p当前是小跳时这个方案才会计入small[i]。当j p当前是大跳时这个方案只计入total[i]不计入small[i]。我上面的代码在jp的分支里同时向sumTotal和sumSmall加了total[prev]这是正确的。在jp的分支里只向sumTotal加了small[prev]。3.2 主递推循环与滑动窗口当i K之后递推的逻辑完全一样但我们有了滑动窗口的优势。我们持续计算i从K1到L的total[i]和small[i]。注意计算total[i]时我们需要i-j的total和small值其中j从1到K所以i-j的范围是[i-K, i-1]。这正是我们维护的“最近K个值”的窗口。实现时我们让数组下标idx i % (K1)。那么(i-j) % (K1)就是(idx - j (K1)) % (K1)。由于j最大为 K这个计算不会越界。主循环结构如下for (long i K1; i L; i) { int idx (int)(i % (K1)); long sumTotal 0; long sumSmall 0; for (int j 1; j K; j) { if (j i) break; // 理论上iK后不会触发但保留更安全 long prevIdx (idx - j (K1)) % (K1); // 计算 (i-j) 对应的循环数组下标 if (j p) { sumTotal (sumTotal total[prevIdx]) % MOD; sumSmall (sumSmall total[prevIdx]) % MOD; } else { sumTotal (sumTotal small[prevIdx]) % MOD; // 大跳不计入small } } total[idx] sumTotal; small[idx] sumSmall; }3.3 最终答案获取与模运算处理当循环进行到i L时我们计算出的total[L % (K1)]就是跳到第 L 格的总方案数也就是我们要求的答案。重要提示模运算因为方案数可能巨大题目要求对 M 取模。在Java中我们应在每次加法后立即取模防止long类型溢出尽管long范围很大但连续累加K次K最大10^5中间值可能溢出。取模运算(a b) % MOD可以写成(a b) % MOD但更安全的写法是(a % MOD b % MOD) % MOD或者使用(a b) % MOD并在之前确保 a, b 都小于 MOD通过及时取模保证。4. 边界条件、陷阱与实战调试这道题思路清晰后实现起来还有不少细节坑一不留神就会WAWrong Answer。4.1 边界条件深度剖析起点定义 (i0)这是最容易出错的地方。我们定义total[0]1,small[0]1。可以理解为“虚拟的起点状态”。当i j即从0直接跳到i时prev i-j 0我们取total[0]或small[0]值都是1这正好对应了“直接跳一次j步”这一种方案。这种初始化是简洁且正确的。p与K的关系题目保证p K。但需要考虑p可能等于0吗从题意看p是“不能连续两次超过p步”如果p0意味着任何大于0的跳都是“大跳”那么就不能连续跳两次这虽然是个边界但算法依然适用。我们的代码中j p和j p的逻辑依然成立。L可能小于K如果L很小我们的主循环可能根本不会执行i从K1开始。因此在初始化阶段i从1到min(L, K)的计算结果可能就已经包含了最终答案。我们需要在初始化后判断如果L K那么答案就是total[L]。所以更稳健的做法是将初始化循环的上限设为min(L, K)。循环数组大小我们设置为K1。为什么是K1而不是K因为我们需要访问prev i-j当jK时prev最小是i-K。为了将i和i-K都映射到数组里且不冲突我们需要K1个位置。可以这样理解我们需要存储最近K个结果加上当前正在计算的这个一共K1个槽位。用取模% (K1)来实现循环覆盖。4.2 常见错误与排查技巧根据我和其他选手的讨论常见的错误点有几个错误1small[i]计算逻辑错误。错误表现结果比标准答案小尤其是当p较小的时候。原因在计算small[i]时错误地只累加了small[prev]。回顾定义small[i]是最后一步为小跳的方案数。因此当j p当前步是小跳时无论上一步是什么这个方案都应该计入small[i]。所以应该加total[prev]而不是small[prev]。small[prev]是上一步为小跳的方案数我们用在上一步来判断当前能否进行大跳。检查方法用小的 L, K, p 手动模拟或者写一个暴力DFS/DP对拍程序验证total和small数组的每一个值。错误2循环数组下标计算错误导致数据污染。错误表现结果不稳定时对时错或者与暴力结果对不上。原因prevIdx计算错误或者total和small数组的更新时机不对。在计算dp[i][j]时我们读取的total[prevIdx]和small[prevIdx]必须是i-j位置最终的、不再改变的值。在我们的循环中i是递增的i-j一定小于i所以当我们计算到i时i-j位置的值肯定已经计算完毕并且存储在循环数组的某个位置了。关键在于这个位置不能被当前轮次的计算覆盖。我们使用(idx - j (K1)) % (K1)来计算并确保数组大小是K1就能保证prevIdx不会等于当前正在计算的idx因为j 1。检查方法打印出前几轮循环中i,idx,j,prevIdx,total[prevIdx],small[prevIdx]的值与手动计算或暴力程序的结果对比。错误3整数溢出和模运算错误。错误表现结果出现负数或者与标准答案对不上模。原因中间累加没有及时取模导致long溢出变成负数再取模结果就错了。或者取模运算的括号没加对。检查方法使用(a b) % MOD的写法并确保在累加每一步都取模。在Java中可以写sumTotal (sumTotal value) % MOD;。对于减法取模要加上MOD再取模(a - b MOD) % MOD。错误4忽略了L很大的情况使用了O(L)的数组。错误表现内存超限MLE。原因直接声明了long[L1]的数组当 L10^18 时不可能。检查方法确认你的数组大小只与 K 有关是O(K)级别的。4.3 性能优化小技巧虽然我们已将空间优化到 O(K)但时间复杂度仍是 O(LK)。当 K 也很大比如接近10^5而 L 也很大时O(LK) 是不可接受的。我们需要进一步优化时间。观察内层循环for (int j1; jK; j)它求的是长度为 K 的区间和。而total[i]和small[i]的公式可以改写total[i] sum_{j1}^{p} total[i-j] sum_{jp1}^{K} small[i-j]small[i] sum_{j1}^{p} total[i-j]我们发现这两个求和都是对固定长度区间[i-K, i-1]内不同数组的求和。我们可以维护total和small数组的前缀和从而在 O(1) 时间内得到区间和。定义preSumTotal[i] sum_{x0}^{i} total[x]preSumSmall[i] sum_{x0}^{i} small[x]那么sum_{j1}^{p} total[i-j] preSumTotal[i-1] - preSumTotal[i-p-1]sum_{jp1}^{K} small[i-j] preSumSmall[i-p-1] - preSumSmall[i-K-1]注意下标边界这样我们就能将内层循环的 O(K) 优化为 O(1)。总时间复杂度降至 O(L)。结合循环数组我们只需要维护preSumTotal和preSumSmall的滑动窗口即可。这是解决此类“线性递推且带前缀和”问题的标准优化在竞赛中非常常见。实操心得在竞赛中如果 K 不是特别大比如几千以内O(LK) 的算法可能还能勉强通过取决于 L 的大小。但如果 K 达到 10^5 量级O(LK) 必超时。所以掌握这个前缀和优化是非常必要的。在编码时可以先实现 O(L*K) 的版本用于验证思路和对拍确保正确后再改写为 O(L) 的版本。这样步步为营调试起来更轻松。5. 代码实现与测试用例这里给出基于前缀和优化后的最终Java代码框架。注意为了处理循环数组前缀和也需要在循环数组上计算公式会稍微复杂一点本质是维护两个变量记录窗口内的总和。import java.util.Scanner; public class BlueJump { public static void main(String[] args) { Scanner sc new Scanner(System.in); long L sc.nextLong(); // 台阶长度 int K sc.nextInt(); // 最大跳跃步数 int p sc.nextInt(); // 小跳阈值 long MOD 20201114L; // 模数示例 // 循环数组大小设为 K1 int modSize K 1; long[] total new long[modSize]; long[] small new long[modSize]; // 初始化 i0 total[0] 1; small[0] 1; // 维护窗口内 total 和 small 的和用于快速计算 long windowTotalSum 1; // total[0] long windowSmallSum 1; // small[0] // 我们需要一个队列来记录窗口内的值但这里我们手动管理下标 // 更简单的方式直接计算前 min(L, K) 项 int maxInit (int) Math.min(L, K); for (int i 1; i maxInit; i) { int idx i % modSize; long newTotal 0; long newSmall 0; // 计算 sum_{j1}^{p} total[i-j] // 由于我们只有循环数组需要小心计算。 // 我们换一种思路既然iK我们可以直接累加。 // 这里为了清晰先写一个内循环稍后替换为前缀和优化。 for (int j 1; j K; j) { if (j i) break; int prevIdx (idx - j modSize) % modSize; if (j p) { newTotal (newTotal total[prevIdx]) % MOD; newSmall (newSmall total[prevIdx]) % MOD; } else { newTotal (newTotal small[prevIdx]) % MOD; } } total[idx] newTotal; small[idx] newSmall; } // 如果 L K答案已经得出 if (L K) { System.out.println(total[(int)(L % modSize)] % MOD); return; } // 主循环i从K1到L使用前缀和思想优化内层循环 // 我们需要维护 total 和 small 在窗口 [i-K, i-1] 内的和 // 初始化窗口和 long sumTotalWindow 0; long sumSmallWindow 0; for (int j 1; j K; j) { int idx (int)((L - j) % modSize); // 这里只是示意实际需要动态维护 // 实际代码中我们需要在循环中动态更新这两个窗口和 } // 由于维护滑动窗口和需要仔细处理下标代码较长。 // 下面给出一个更清晰但稍慢的版本O(L*K)适用于K不大的情况。 // 对于竞赛建议实现完整的滑动窗口前缀和版本。 for (long i K1; i L; i) { int idx (int)(i % modSize); long newTotal 0; long newSmall 0; // 内循环未优化 for (int j 1; j K; j) { if (j i) break; // 实际不会触发因为iK int prevIdx (idx - j modSize) % modSize; if (j p) { newTotal (newTotal total[prevIdx]) % MOD; newSmall (newSmall total[prevIdx]) % MOD; } else { newTotal (newTotal small[prevIdx]) % MOD; } } total[idx] newTotal; small[idx] newSmall; } System.out.println(total[(int)(L % modSize)] % MOD); sc.close(); } }注意上面的代码主循环部分仍然是 O(L*K) 的仅用于演示逻辑。在实际竞赛中你需要实现滑动窗口维护total和small的区间和将内层循环优化掉。这里为了不偏离核心思路讲解省略了那部分稍显复杂的下标管理代码。其核心是维护两个变量sumTotalWin和sumSmallWin分别记录total和small在窗口[i-K, i-1]内的和。当i增加时从窗口尾部移除i-K-1位置的值并向头部添加i-1位置的值。最后分享一个调试技巧对于动态规划问题尤其是带模运算的一定要自己构造小数据测试。比如令 L5, K3, p1手工计算所有方案然后与程序输出对比。或者写一个暴力DFS搜索所有路径的程序用于对拍。只有在小数据上完全正确才能保证在大数据上的逻辑正确性。模运算的检查可以尝试不同的模数看结果是否合理。这道题“蓝跳跳”融合了动态规划、状态设计、循环数组优化和前缀和思想是一道锻炼综合能力的好题搞懂了它你对DP的理解会上一个台阶。