1. 项目概述当质数遇上三维迷宫如果你参加过蓝桥杯或者刷过一些算法竞赛题大概率对“走格子”类的动态规划DP不陌生。从最简单的二维网格路径计数到加上一些障碍物限制这类题目考察的是对状态定义和转移方程的把握。但“质数行者”这道题把经典的“走格子”模型玩出了新花样直接推到了三维空间并且给每一步的移动加上了“质数步长”这个强约束。我第一次看到这个题时感觉就像在玩一个三维的、规则特殊的跳棋你的棋子不能随意走只能沿着坐标轴方向跳跃质数格的距离。题目核心可以这样理解在一个三维空间(X, Y, Z)中起点是(1,1,1)终点是(n, m, w)。行者每一步必须选择 X、Y、Z 三个轴向中的一个并且沿着该轴向正方向移动一个质数长度的距离。比如在X轴上可以移动2格、3格、5格、7格……但不能移动1格1不是质数、4格合数或6格合数。目标就是计算出从起点到终点的所有可能路径总数结果通常需要对一个大数如1e97取模。这题出现在蓝桥杯决赛其难度在于它融合了多个知识点三维空间的状态表示、坐标型动态规划、质数筛法与预处理以及对大数取模运算的处理。它不再是简单的二维递推你需要同时维护三个维度上的进度它也不再是步长为1你需要动态判断哪些步长是合法的。用C语言来实现更是对编程者基础功的考验包括数组内存管理、循环优化和模运算细节。下面我就结合自己的解题经验把这题的“里里外外”拆解清楚从思路到代码从核心原理到避坑指南给你讲透。2. 核心思路拆解如何降维思考三维问题面对三维DP新手最容易懵的地方就是状态数组的定义。二维DP我们常用dp[i][j]那三维很自然就是dp[i][j][k]。对于本题dp[x][y][z]可以定义为从起点(1,1,1)走到坐标(x, y, z)的所有不同路径数。2.1 状态转移方程的推导确定了状态接下来就是最关键的状态转移方程。既然每一步只能沿一个轴走一个质数步长那么要到达(x, y, z)最后一步只可能是三种情况最后一步是沿X轴走过来的那么上一步的坐标就是(x-p, y, z)其中p是一个质数并且满足x-p 1。最后一步是沿Y轴走过来的那么上一步的坐标是(x, y-p, z)。最后一步是沿Z轴走过来的那么上一步的坐标是(x, y, z-p)。因此到达当前点的路径数就等于所有可能的上一点路径数的总和。用方程表示就是dp[x][y][z] Σ dp[x-p][y][z] Σ dp[x][y-p][z] Σ dp[x][y][z-p]其中每一个Σ都是对所有满足条件的质数p进行求和且要确保x-p,y-p,z-p不小于1即不越界。注意这里有一个非常重要的初始化。起点(1,1,1)本身就算一条路径“不动”也算一种方案吗在路径计数问题中起点状态通常初始化为1表示一种“已经在此”的初始状态。所以dp[1][1][1] 1。2.2 质数表的预处理性能的关键直接在每个状态转移时都去判断一个数p是不是质数时间复杂度是不可接受的。假设三维最大坐标为N那么我们需要判断1到N之间所有数是否为质数并且这个判断会被执行非常多次。标准的做法是在DP开始前先用埃拉托斯特尼筛法埃氏筛或线性筛预处理出1到MAX_NMAX_N是n, m, w中的最大值范围内的所有质数并存储在一个数组或一个布尔型标记数组中。埃氏筛实现简单效率对于本题数据范围通常坐标不超过几百完全足够。其原理是从2开始将每个质数的倍数标记为合数。#define MAX_N 1000 // 根据题目数据范围设定 int is_prime[MAX_N 1]; void sieve() { for (int i 2; i MAX_N; i) is_prime[i] 1; for (int i 2; i * i MAX_N; i) { if (is_prime[i]) { for (int j i * i; j MAX_N; j i) { is_prime[j] 0; } } } is_prime[1] 0; // 1不是质数 }线性筛效率更高能确保每个合数只被其最小质因子筛掉一次适合数据范围更大的情况。但对于蓝桥杯环境埃氏筛通常够用且更不易写错。预处理后我们在状态转移时只需要遍历一个从2到当前坐标值的质数列表或者通过is_prime[p]快速判断p是否为质数即可。2.3 复杂度分析与优化思考最朴素的实现是三层循环遍历x, y, z在每层内部还要遍历所有可能的质数p。时间复杂度约为O(N^3 * P)其中P是小于N的质数个数约为N/lnN。当N300时这个计算量可能就在时间边缘了。一个重要的优化点是我们并不需要每次都遍历到x或y, z的所有质数。因为步长p必须小于当前坐标x否则x-p1。所以内层循环质数时上限是x-1对于X轴。更进一步我们可以提前将质数存储在一个数组primes[]里并记录其个数primeCount这样内层循环就是遍历primes[]数组直到primes[j] x。3. 代码实现与逐行解析理解了思路我们来看C语言的具体实现。我会用一个结构清晰的版本来讲解。3.1 头文件、常量与全局变量#include stdio.h #include string.h #define MOD 1000000007 // 常见的模数 #define MAX_N 305 // 假设坐标最大值根据题目调整 int n, m, w; // 终点坐标 (n, m, w) int dp[MAX_N][MAX_N][MAX_N]; // 三维DP数组 int is_prime[MAX_N 1]; // 质数标记数组 int primes[MAX_N]; // 存储质数的数组 int primeCount 0; // 质数个数MOD结果取模的值1e97是一个大质数常用于避免整数溢出。MAX_N数组大小。这里是一个关键坑点题目给的n, m, w是终点坐标我们的DP数组下标需要访问到n, m, w因此数组声明至少要是[n1][m1][w1]。为了安全通常直接开一个稍大的固定尺寸如305。如果使用变长数组C99支持会更节省内存但要注意编译器支持情况。dp数组核心状态数组。类型为int但计算过程中可能超过int范围吗由于每一步都取模且MOD是1e97两个小于MOD的数相加不会超过2e9仍在int范围内int通常是32位最大约21亿。但为了绝对安全有些人会用long long。这里用int并在每次加法后取模是可行的。is_prime和primes用于质数处理。3.2 质数筛法实现我们采用埃氏筛并将筛出的质数存入primes数组方便后续遍历。void init_primes(int limit) { // 初始化假设所有数都是质数 for (int i 2; i limit; i) { is_prime[i] 1; } is_prime[0] is_prime[1] 0; // 0和1不是质数 for (int i 2; i * i limit; i) { if (is_prime[i]) { // 将质数存入列表 primes[primeCount] i; // 筛去质数i的倍数 for (int j i * i; j limit; j i) { is_prime[j] 0; } } } // 处理剩余大于sqrt(limit)的质数 for (int i (int)sqrt(limit) 1; i limit; i) { if (is_prime[i]) { primes[primeCount] i; } } }实操心得埃氏筛的内层循环从i*i开始是因为小于i*i的合数已经被更小的质数筛过了。这是标准的优化能减少冗余操作。另外先存质数再筛或者像我上面这样在筛的过程中存都是可以的。最后那个循环是为了收集那些大于sqrt(limit)的质数它们没有被前面的循环加入到primes数组中。3.3 核心DP过程这是代码的心脏部分。我们需要三重循环来遍历所有三维坐标状态。void solve() { // 初始化DP数组为0 memset(dp, 0, sizeof(dp)); // 起点方案数为1 dp[1][1][1] 1; // 三重循环遍历所有状态 for (int x 1; x n; x) { for (int y 1; y m; y) { for (int z 1; z w; z) { // 如果当前点是起点跳过因为起点已经初始化且从起点转移无意义 if (x 1 y 1 z 1) { continue; } long long ways 0; // 临时变量用long long防止中间结果溢出 // 情况1最后一步从X轴方向走来 for (int idx 0; idx primeCount; idx) { int p primes[idx]; if (p x) break; // 步长不能大于等于当前坐标 ways dp[x - p][y][z]; } // 情况2最后一步从Y轴方向走来 for (int idx 0; idx primeCount; idx) { int p primes[idx]; if (p y) break; ways dp[x][y - p][z]; } // 情况3最后一步从Z轴方向走来 for (int idx 0; idx primeCount; idx) { int p primes[idx]; if (p z) break; ways dp[x][y][z - p]; } // 取模并赋值给dp数组 dp[x][y][z] ways % MOD; } } } // 输出终点结果 printf(%d\n, dp[n][m][w]); }逐行解析与关键点memset(dp, 0, sizeof(dp))清空DP数组是良好习惯。虽然我们后续会覆盖所有值但确保初始状态为0是安全的。dp[1][1][1] 1状态初始化。这是动态规划的“基石”表示在起点有一种方案。三重循环顺序这里按照x,y,z的顺序遍历。这保证了当我们计算dp[x][y][z]时它所依赖的状态dp[x-p][y][z]、dp[x][y-p][z]和dp[x][y][z-p]都已经被计算出来了。因为p2所以x-p x之前的循环一定已经处理过。这是坐标型DP的典型特征——按坐标顺序递推。跳过起点起点已经初始化且从起点转移到起点没有意义需要步长p为0但0不是质数所以直接continue。使用long long ways这是一个重要的技巧。在累加多个dp值的过程中即使每个dp值都小于MOD但很多个加起来可能会超过int范围。先用long long累加最后再取模可以避免中间溢出。内层质数循环遍历primes数组一旦质数p不小于当前坐标p x就立即break。因为质数数组是递增的后面的质数只会更大不可能满足条件。这减少了不必要的循环。取模运算dp[x][y][z] ways % MOD;将最终结果存回int类型的dp数组。由于ways已经取模结果一定在[0, MOD)范围内赋值给int是安全的。3.4 主函数与完整流程int main() { // 假设从标准输入读取终点坐标 scanf(%d %d %d, n, m, w); // 确定质数筛的范围需要筛到 max(n, m, w) int max_coord n; if (m max_coord) max_coord m; if (w max_coord) max_coord w; // 初始化质数表 init_primes(max_coord); // 执行DP求解 solve(); return 0; }主函数逻辑清晰读入数据确定质数筛的范围需要覆盖所有坐标轴可能用到的质数初始化质数表然后调用求解函数。4. 边界条件与易错点深度剖析即使思路正确实现时也极易踩坑。下面这些点是我在调试和教学过程中总结出来的。4.1 数组越界无声的杀手这是C语言做DP题最常见的错误之一。dp数组大小声明为dp[MAX_N][MAX_N][MAX_N]但你的n, m, w可能等于MAX_N。在循环中你会访问dp[n][m][w]如果数组大小正好是MAX_N那么下标范围是0到MAX_N-1访问MAX_N就越界了。所以数组大小至少要是MAX_N1。在我的代码中#define MAX_N 305而数组声明为dp[MAX_N][MAX_N][MAX_N]实际上能安全访问的最大下标是304。如果题目坐标上限是300那没问题。但如果上限是500这里就会崩溃。更安全的做法是使用变长数组VLA或者根据输入动态分配内存。// 动态分配更安全但稍复杂 int (*dp)[m1][w1] (int(*)[m1][w1])malloc((n1) * sizeof(int[m1][w1])); // 使用后记得 free(dp);质数筛数组越界在init_primes函数中循环条件i * i limit如果limit很大i*i可能溢出。通常题目范围下没问题但要知道这个风险。可以用i limit/i来判断。状态转移中的越界在计算dp[x-p][y][z]时我们通过if (p x) break;来保证x-p 1。但请注意数组下标是从0开始的而我们的逻辑坐标是从1开始的。dp[0][y][z]这个位置我们从未初始化也不应该被访问。我们的break条件p x确保了x-p 0时不会进入循环体从而避免了访问dp[0][...]。这一点必须仔细检查。4.2 模运算的陷阱负数的模C语言中%运算符对负数取模的结果是负数或与实现相关。但在我们的算法中所有数都是非负的所以不会遇到。然而如果你在减法后取模比如题目要求路径数相减就需要使用(a - b MOD) % MOD来确保结果非负。加法溢出如前所述使用long long临时变量来累加是稳妥的做法。不要依赖int的溢出行为。4.3 时间与空间复杂度的权衡空间三维数组非常耗内存。dp[305][305][305]大约需要305*305*305*4字节 ≈ 113MB这已经接近甚至超过一些竞赛环境的默认栈内存限制通常栈空间较小。全局数组在静态存储区而函数内的大数组在栈上。将dp数组声明为全局变量如我所做是解决大数组问题的常用方法因为全局变量在内存的数据段空间通常更大。如果声明在main或solve函数内部很可能导致栈溢出。时间我们的算法复杂度约为O(n*m*w*P)其中P是平均每个坐标需要遍历的质数个数。当n,m,w在200左右时运算量在千万到亿次级别在C语言和现代CPU上通常是1秒内。但如果达到300或更大就可能超时。这时需要考虑优化比如用前缀和思想不这里不太适用。更实际的优化是压缩质数遍历我们内层循环每次都是从质数表头开始遍历。可以预处理出对于每个坐标x有哪些质数p x并存储其索引这样内层循环就直接遍历这个更小的列表。但这会增加编码复杂度。4.4 初始化与起点的理解dp[1][1][1] 1是必须的。可以这样理解当行者在起点时有一种“已经到达”的方案。如果初始化为0那么所有状态都无法从起点转移出来结果永远是0。5. 测试与调试如何验证你的代码写完代码不要急着提交自己构造几个测试用例。测试用例设计最小情况n1, m1, w1。起点即终点。答案应该是1。你的代码能处理吗注意我们的循环从1开始并且跳过了(1,1,1)点但最终dp[1][1][1]在初始化时就是1所以输出是1。简单可手算情况n3, m1, w1。终点在(3,1,1)。从(1,1,1)只能沿X轴走。质数步长有2。所以只有一种走法(1,1,1) - (3,1,1)。答案应为1。手动模拟DPdp[1][1][1]1dp[2][1][1]: 从X轴来需要p1非质数或p2但22break。从Y、Z轴来需要p1。所以为0。dp[3][1][1]: 从X轴来p223来自dp[1][1][1]1。其他轴无贡献。所以为1。稍复杂情况n4, m1, w1。终点(4,1,1)。可能路径(1,1,1) - (3,1,1) - (4,1,1)不对第二步从(3,1,1)到(4,1,1)需要走1步不是质数。实际上从(1,1,1)到(4,1,1)只能一步到位走质数步长3。所以只有一种走法。答案应为1。再检查n5, m1, w1到(5,1,1)。质数步长有2和3。走2步从(3,1,1)来。dp[3][1][1]我们刚算过是1。走3步从(2,1,1)来。dp[2][1][1]是0。所以dp[5][1][1] 1。二维情况帮助理解可以先把w固定为1测试二维下的结果。例如n3, m3, w1。相当于在3x3的网格上只能走质数步。可以手工画图枚举一下。调试技巧打印中间状态对于小的测试用例可以在DP循环中打印出dp数组的部分值与你的手算结果对比。比如打印所有dp[x][1][1]的值。检查质数表确保你的init_primes函数正确筛出了质数。可以打印primes数组的前20个看看。使用调试器设置断点观察变量值的变化这是定位逻辑错误最有效的方法。6. 进阶思考与优化方向虽然上面的代码已经可以解决很多情况下的题目但追求极致总是有趣的。6.1 空间优化滚动数组三维DP的空间消耗是O(N^3)。我们能否优化观察状态转移方程dp[x][y][z]只依赖于x,y,z三者中某一维减小的状态。这似乎不具备明显的维度压缩特性。对于“质数行者”这种三个维度完全对称且转移依赖所有历史状态的题目很难使用滚动数组将三维压缩到二维。因为更新(x,y,z)时可能需要(x-p, y, z)等状态而x-p可能比x小很多如果压缩了x维度这些历史信息就被覆盖了。所以空间优化在这里的优先级不高除非题目数据范围极大比如n,m,w 500导致内存超限。那时可能需要考虑更复杂的压缩方法或者换用其他算法如记忆化搜索。6.2 时间优化预处理转移列表当前最耗时的部分是内层对质数的遍历。对于每个坐标(x,y,z)我们都要遍历质数表直到p x或y, z。实际上对于每个坐标值v可以是x, y, z哪些质数p v是固定的。我们可以预先处理一个“转移列表”数组vectorint trans[MAX_N]在C中可以用静态数组加长度记录。trans[v]存储所有小于v的质数。这样在DP循环中对于dp[x][y][z]我们不需要遍历整个质数表而是直接遍历trans[x],trans[y],trans[z]这三个小列表。这能减少大量不必要的比较操作。// 预处理转移列表 int trans[MAX_N][MAX_N]; // trans[v][0]存储列表长度后面存储质数 int trans_len[MAX_N] {0}; void init_trans(int limit) { for (int v 2; v limit; v) { int len 0; for (int idx 0; idx primeCount; idx) { int p primes[idx]; if (p v) break; trans[v][len] p; // trans[v][0]不用从1开始存 } trans[v][0] len; // 把长度存在第一个位置 trans_len[v] len; } } // 在DP中遍历X轴方向时 for (int idx 1; idx trans_len[x]; idx) { int p trans[x][idx]; ways dp[x - p][y][z]; }这种优化在坐标范围较大时效果明显。6.3 算法变种思考如果题目不是求到终点的路径数而是求“恰好走K步”到达终点的方案数或者每个点有“陷阱”不能经过那又该如何这就会变成更复杂的DP可能需要增加“步数”维度或者用BFS结合DP。但核心的“质数步长”和“三维坐标”思想是不变的。7. 从这道题延伸的DP学习建议“质数行者”是一道非常好的综合练习题。它巩固了几个关键概念状态定义在三维空间中用坐标(x,y,z)来定义状态是直观的。DP的核心就是找到那一个或一组能完整描述当前“局面”的变量。状态转移分析最后一步的可能性将大问题分解为子问题。这是构建转移方程的通用思路。预处理DP经常需要配合预处理如本题的质数筛。将不变或可提前计算的信息准备好能极大提升主算法效率。边界与初始化起点的dp[1][1][1]1是正确计数的保证。要仔细思考“原点”状态的含义。复杂度分析能帮助你判断算法是否可行并指导优化方向。对于想深入掌握DP的同学我的建议是多画图多模拟。对于三维问题可以在纸上固定一维画出另外两维的表格手动推导几个状态的值。理解状态之间是如何“流动”的。然后一定要动手实现并尝试用不同的测试用例去“攻击”你的代码思考各种边界情况。像“质数行者”这样的题吃透一道胜过模糊地看十道。
三维动态规划与质数步长：蓝桥杯“质数行者”算法精解
1. 项目概述当质数遇上三维迷宫如果你参加过蓝桥杯或者刷过一些算法竞赛题大概率对“走格子”类的动态规划DP不陌生。从最简单的二维网格路径计数到加上一些障碍物限制这类题目考察的是对状态定义和转移方程的把握。但“质数行者”这道题把经典的“走格子”模型玩出了新花样直接推到了三维空间并且给每一步的移动加上了“质数步长”这个强约束。我第一次看到这个题时感觉就像在玩一个三维的、规则特殊的跳棋你的棋子不能随意走只能沿着坐标轴方向跳跃质数格的距离。题目核心可以这样理解在一个三维空间(X, Y, Z)中起点是(1,1,1)终点是(n, m, w)。行者每一步必须选择 X、Y、Z 三个轴向中的一个并且沿着该轴向正方向移动一个质数长度的距离。比如在X轴上可以移动2格、3格、5格、7格……但不能移动1格1不是质数、4格合数或6格合数。目标就是计算出从起点到终点的所有可能路径总数结果通常需要对一个大数如1e97取模。这题出现在蓝桥杯决赛其难度在于它融合了多个知识点三维空间的状态表示、坐标型动态规划、质数筛法与预处理以及对大数取模运算的处理。它不再是简单的二维递推你需要同时维护三个维度上的进度它也不再是步长为1你需要动态判断哪些步长是合法的。用C语言来实现更是对编程者基础功的考验包括数组内存管理、循环优化和模运算细节。下面我就结合自己的解题经验把这题的“里里外外”拆解清楚从思路到代码从核心原理到避坑指南给你讲透。2. 核心思路拆解如何降维思考三维问题面对三维DP新手最容易懵的地方就是状态数组的定义。二维DP我们常用dp[i][j]那三维很自然就是dp[i][j][k]。对于本题dp[x][y][z]可以定义为从起点(1,1,1)走到坐标(x, y, z)的所有不同路径数。2.1 状态转移方程的推导确定了状态接下来就是最关键的状态转移方程。既然每一步只能沿一个轴走一个质数步长那么要到达(x, y, z)最后一步只可能是三种情况最后一步是沿X轴走过来的那么上一步的坐标就是(x-p, y, z)其中p是一个质数并且满足x-p 1。最后一步是沿Y轴走过来的那么上一步的坐标是(x, y-p, z)。最后一步是沿Z轴走过来的那么上一步的坐标是(x, y, z-p)。因此到达当前点的路径数就等于所有可能的上一点路径数的总和。用方程表示就是dp[x][y][z] Σ dp[x-p][y][z] Σ dp[x][y-p][z] Σ dp[x][y][z-p]其中每一个Σ都是对所有满足条件的质数p进行求和且要确保x-p,y-p,z-p不小于1即不越界。注意这里有一个非常重要的初始化。起点(1,1,1)本身就算一条路径“不动”也算一种方案吗在路径计数问题中起点状态通常初始化为1表示一种“已经在此”的初始状态。所以dp[1][1][1] 1。2.2 质数表的预处理性能的关键直接在每个状态转移时都去判断一个数p是不是质数时间复杂度是不可接受的。假设三维最大坐标为N那么我们需要判断1到N之间所有数是否为质数并且这个判断会被执行非常多次。标准的做法是在DP开始前先用埃拉托斯特尼筛法埃氏筛或线性筛预处理出1到MAX_NMAX_N是n, m, w中的最大值范围内的所有质数并存储在一个数组或一个布尔型标记数组中。埃氏筛实现简单效率对于本题数据范围通常坐标不超过几百完全足够。其原理是从2开始将每个质数的倍数标记为合数。#define MAX_N 1000 // 根据题目数据范围设定 int is_prime[MAX_N 1]; void sieve() { for (int i 2; i MAX_N; i) is_prime[i] 1; for (int i 2; i * i MAX_N; i) { if (is_prime[i]) { for (int j i * i; j MAX_N; j i) { is_prime[j] 0; } } } is_prime[1] 0; // 1不是质数 }线性筛效率更高能确保每个合数只被其最小质因子筛掉一次适合数据范围更大的情况。但对于蓝桥杯环境埃氏筛通常够用且更不易写错。预处理后我们在状态转移时只需要遍历一个从2到当前坐标值的质数列表或者通过is_prime[p]快速判断p是否为质数即可。2.3 复杂度分析与优化思考最朴素的实现是三层循环遍历x, y, z在每层内部还要遍历所有可能的质数p。时间复杂度约为O(N^3 * P)其中P是小于N的质数个数约为N/lnN。当N300时这个计算量可能就在时间边缘了。一个重要的优化点是我们并不需要每次都遍历到x或y, z的所有质数。因为步长p必须小于当前坐标x否则x-p1。所以内层循环质数时上限是x-1对于X轴。更进一步我们可以提前将质数存储在一个数组primes[]里并记录其个数primeCount这样内层循环就是遍历primes[]数组直到primes[j] x。3. 代码实现与逐行解析理解了思路我们来看C语言的具体实现。我会用一个结构清晰的版本来讲解。3.1 头文件、常量与全局变量#include stdio.h #include string.h #define MOD 1000000007 // 常见的模数 #define MAX_N 305 // 假设坐标最大值根据题目调整 int n, m, w; // 终点坐标 (n, m, w) int dp[MAX_N][MAX_N][MAX_N]; // 三维DP数组 int is_prime[MAX_N 1]; // 质数标记数组 int primes[MAX_N]; // 存储质数的数组 int primeCount 0; // 质数个数MOD结果取模的值1e97是一个大质数常用于避免整数溢出。MAX_N数组大小。这里是一个关键坑点题目给的n, m, w是终点坐标我们的DP数组下标需要访问到n, m, w因此数组声明至少要是[n1][m1][w1]。为了安全通常直接开一个稍大的固定尺寸如305。如果使用变长数组C99支持会更节省内存但要注意编译器支持情况。dp数组核心状态数组。类型为int但计算过程中可能超过int范围吗由于每一步都取模且MOD是1e97两个小于MOD的数相加不会超过2e9仍在int范围内int通常是32位最大约21亿。但为了绝对安全有些人会用long long。这里用int并在每次加法后取模是可行的。is_prime和primes用于质数处理。3.2 质数筛法实现我们采用埃氏筛并将筛出的质数存入primes数组方便后续遍历。void init_primes(int limit) { // 初始化假设所有数都是质数 for (int i 2; i limit; i) { is_prime[i] 1; } is_prime[0] is_prime[1] 0; // 0和1不是质数 for (int i 2; i * i limit; i) { if (is_prime[i]) { // 将质数存入列表 primes[primeCount] i; // 筛去质数i的倍数 for (int j i * i; j limit; j i) { is_prime[j] 0; } } } // 处理剩余大于sqrt(limit)的质数 for (int i (int)sqrt(limit) 1; i limit; i) { if (is_prime[i]) { primes[primeCount] i; } } }实操心得埃氏筛的内层循环从i*i开始是因为小于i*i的合数已经被更小的质数筛过了。这是标准的优化能减少冗余操作。另外先存质数再筛或者像我上面这样在筛的过程中存都是可以的。最后那个循环是为了收集那些大于sqrt(limit)的质数它们没有被前面的循环加入到primes数组中。3.3 核心DP过程这是代码的心脏部分。我们需要三重循环来遍历所有三维坐标状态。void solve() { // 初始化DP数组为0 memset(dp, 0, sizeof(dp)); // 起点方案数为1 dp[1][1][1] 1; // 三重循环遍历所有状态 for (int x 1; x n; x) { for (int y 1; y m; y) { for (int z 1; z w; z) { // 如果当前点是起点跳过因为起点已经初始化且从起点转移无意义 if (x 1 y 1 z 1) { continue; } long long ways 0; // 临时变量用long long防止中间结果溢出 // 情况1最后一步从X轴方向走来 for (int idx 0; idx primeCount; idx) { int p primes[idx]; if (p x) break; // 步长不能大于等于当前坐标 ways dp[x - p][y][z]; } // 情况2最后一步从Y轴方向走来 for (int idx 0; idx primeCount; idx) { int p primes[idx]; if (p y) break; ways dp[x][y - p][z]; } // 情况3最后一步从Z轴方向走来 for (int idx 0; idx primeCount; idx) { int p primes[idx]; if (p z) break; ways dp[x][y][z - p]; } // 取模并赋值给dp数组 dp[x][y][z] ways % MOD; } } } // 输出终点结果 printf(%d\n, dp[n][m][w]); }逐行解析与关键点memset(dp, 0, sizeof(dp))清空DP数组是良好习惯。虽然我们后续会覆盖所有值但确保初始状态为0是安全的。dp[1][1][1] 1状态初始化。这是动态规划的“基石”表示在起点有一种方案。三重循环顺序这里按照x,y,z的顺序遍历。这保证了当我们计算dp[x][y][z]时它所依赖的状态dp[x-p][y][z]、dp[x][y-p][z]和dp[x][y][z-p]都已经被计算出来了。因为p2所以x-p x之前的循环一定已经处理过。这是坐标型DP的典型特征——按坐标顺序递推。跳过起点起点已经初始化且从起点转移到起点没有意义需要步长p为0但0不是质数所以直接continue。使用long long ways这是一个重要的技巧。在累加多个dp值的过程中即使每个dp值都小于MOD但很多个加起来可能会超过int范围。先用long long累加最后再取模可以避免中间溢出。内层质数循环遍历primes数组一旦质数p不小于当前坐标p x就立即break。因为质数数组是递增的后面的质数只会更大不可能满足条件。这减少了不必要的循环。取模运算dp[x][y][z] ways % MOD;将最终结果存回int类型的dp数组。由于ways已经取模结果一定在[0, MOD)范围内赋值给int是安全的。3.4 主函数与完整流程int main() { // 假设从标准输入读取终点坐标 scanf(%d %d %d, n, m, w); // 确定质数筛的范围需要筛到 max(n, m, w) int max_coord n; if (m max_coord) max_coord m; if (w max_coord) max_coord w; // 初始化质数表 init_primes(max_coord); // 执行DP求解 solve(); return 0; }主函数逻辑清晰读入数据确定质数筛的范围需要覆盖所有坐标轴可能用到的质数初始化质数表然后调用求解函数。4. 边界条件与易错点深度剖析即使思路正确实现时也极易踩坑。下面这些点是我在调试和教学过程中总结出来的。4.1 数组越界无声的杀手这是C语言做DP题最常见的错误之一。dp数组大小声明为dp[MAX_N][MAX_N][MAX_N]但你的n, m, w可能等于MAX_N。在循环中你会访问dp[n][m][w]如果数组大小正好是MAX_N那么下标范围是0到MAX_N-1访问MAX_N就越界了。所以数组大小至少要是MAX_N1。在我的代码中#define MAX_N 305而数组声明为dp[MAX_N][MAX_N][MAX_N]实际上能安全访问的最大下标是304。如果题目坐标上限是300那没问题。但如果上限是500这里就会崩溃。更安全的做法是使用变长数组VLA或者根据输入动态分配内存。// 动态分配更安全但稍复杂 int (*dp)[m1][w1] (int(*)[m1][w1])malloc((n1) * sizeof(int[m1][w1])); // 使用后记得 free(dp);质数筛数组越界在init_primes函数中循环条件i * i limit如果limit很大i*i可能溢出。通常题目范围下没问题但要知道这个风险。可以用i limit/i来判断。状态转移中的越界在计算dp[x-p][y][z]时我们通过if (p x) break;来保证x-p 1。但请注意数组下标是从0开始的而我们的逻辑坐标是从1开始的。dp[0][y][z]这个位置我们从未初始化也不应该被访问。我们的break条件p x确保了x-p 0时不会进入循环体从而避免了访问dp[0][...]。这一点必须仔细检查。4.2 模运算的陷阱负数的模C语言中%运算符对负数取模的结果是负数或与实现相关。但在我们的算法中所有数都是非负的所以不会遇到。然而如果你在减法后取模比如题目要求路径数相减就需要使用(a - b MOD) % MOD来确保结果非负。加法溢出如前所述使用long long临时变量来累加是稳妥的做法。不要依赖int的溢出行为。4.3 时间与空间复杂度的权衡空间三维数组非常耗内存。dp[305][305][305]大约需要305*305*305*4字节 ≈ 113MB这已经接近甚至超过一些竞赛环境的默认栈内存限制通常栈空间较小。全局数组在静态存储区而函数内的大数组在栈上。将dp数组声明为全局变量如我所做是解决大数组问题的常用方法因为全局变量在内存的数据段空间通常更大。如果声明在main或solve函数内部很可能导致栈溢出。时间我们的算法复杂度约为O(n*m*w*P)其中P是平均每个坐标需要遍历的质数个数。当n,m,w在200左右时运算量在千万到亿次级别在C语言和现代CPU上通常是1秒内。但如果达到300或更大就可能超时。这时需要考虑优化比如用前缀和思想不这里不太适用。更实际的优化是压缩质数遍历我们内层循环每次都是从质数表头开始遍历。可以预处理出对于每个坐标x有哪些质数p x并存储其索引这样内层循环就直接遍历这个更小的列表。但这会增加编码复杂度。4.4 初始化与起点的理解dp[1][1][1] 1是必须的。可以这样理解当行者在起点时有一种“已经到达”的方案。如果初始化为0那么所有状态都无法从起点转移出来结果永远是0。5. 测试与调试如何验证你的代码写完代码不要急着提交自己构造几个测试用例。测试用例设计最小情况n1, m1, w1。起点即终点。答案应该是1。你的代码能处理吗注意我们的循环从1开始并且跳过了(1,1,1)点但最终dp[1][1][1]在初始化时就是1所以输出是1。简单可手算情况n3, m1, w1。终点在(3,1,1)。从(1,1,1)只能沿X轴走。质数步长有2。所以只有一种走法(1,1,1) - (3,1,1)。答案应为1。手动模拟DPdp[1][1][1]1dp[2][1][1]: 从X轴来需要p1非质数或p2但22break。从Y、Z轴来需要p1。所以为0。dp[3][1][1]: 从X轴来p223来自dp[1][1][1]1。其他轴无贡献。所以为1。稍复杂情况n4, m1, w1。终点(4,1,1)。可能路径(1,1,1) - (3,1,1) - (4,1,1)不对第二步从(3,1,1)到(4,1,1)需要走1步不是质数。实际上从(1,1,1)到(4,1,1)只能一步到位走质数步长3。所以只有一种走法。答案应为1。再检查n5, m1, w1到(5,1,1)。质数步长有2和3。走2步从(3,1,1)来。dp[3][1][1]我们刚算过是1。走3步从(2,1,1)来。dp[2][1][1]是0。所以dp[5][1][1] 1。二维情况帮助理解可以先把w固定为1测试二维下的结果。例如n3, m3, w1。相当于在3x3的网格上只能走质数步。可以手工画图枚举一下。调试技巧打印中间状态对于小的测试用例可以在DP循环中打印出dp数组的部分值与你的手算结果对比。比如打印所有dp[x][1][1]的值。检查质数表确保你的init_primes函数正确筛出了质数。可以打印primes数组的前20个看看。使用调试器设置断点观察变量值的变化这是定位逻辑错误最有效的方法。6. 进阶思考与优化方向虽然上面的代码已经可以解决很多情况下的题目但追求极致总是有趣的。6.1 空间优化滚动数组三维DP的空间消耗是O(N^3)。我们能否优化观察状态转移方程dp[x][y][z]只依赖于x,y,z三者中某一维减小的状态。这似乎不具备明显的维度压缩特性。对于“质数行者”这种三个维度完全对称且转移依赖所有历史状态的题目很难使用滚动数组将三维压缩到二维。因为更新(x,y,z)时可能需要(x-p, y, z)等状态而x-p可能比x小很多如果压缩了x维度这些历史信息就被覆盖了。所以空间优化在这里的优先级不高除非题目数据范围极大比如n,m,w 500导致内存超限。那时可能需要考虑更复杂的压缩方法或者换用其他算法如记忆化搜索。6.2 时间优化预处理转移列表当前最耗时的部分是内层对质数的遍历。对于每个坐标(x,y,z)我们都要遍历质数表直到p x或y, z。实际上对于每个坐标值v可以是x, y, z哪些质数p v是固定的。我们可以预先处理一个“转移列表”数组vectorint trans[MAX_N]在C中可以用静态数组加长度记录。trans[v]存储所有小于v的质数。这样在DP循环中对于dp[x][y][z]我们不需要遍历整个质数表而是直接遍历trans[x],trans[y],trans[z]这三个小列表。这能减少大量不必要的比较操作。// 预处理转移列表 int trans[MAX_N][MAX_N]; // trans[v][0]存储列表长度后面存储质数 int trans_len[MAX_N] {0}; void init_trans(int limit) { for (int v 2; v limit; v) { int len 0; for (int idx 0; idx primeCount; idx) { int p primes[idx]; if (p v) break; trans[v][len] p; // trans[v][0]不用从1开始存 } trans[v][0] len; // 把长度存在第一个位置 trans_len[v] len; } } // 在DP中遍历X轴方向时 for (int idx 1; idx trans_len[x]; idx) { int p trans[x][idx]; ways dp[x - p][y][z]; }这种优化在坐标范围较大时效果明显。6.3 算法变种思考如果题目不是求到终点的路径数而是求“恰好走K步”到达终点的方案数或者每个点有“陷阱”不能经过那又该如何这就会变成更复杂的DP可能需要增加“步数”维度或者用BFS结合DP。但核心的“质数步长”和“三维坐标”思想是不变的。7. 从这道题延伸的DP学习建议“质数行者”是一道非常好的综合练习题。它巩固了几个关键概念状态定义在三维空间中用坐标(x,y,z)来定义状态是直观的。DP的核心就是找到那一个或一组能完整描述当前“局面”的变量。状态转移分析最后一步的可能性将大问题分解为子问题。这是构建转移方程的通用思路。预处理DP经常需要配合预处理如本题的质数筛。将不变或可提前计算的信息准备好能极大提升主算法效率。边界与初始化起点的dp[1][1][1]1是正确计数的保证。要仔细思考“原点”状态的含义。复杂度分析能帮助你判断算法是否可行并指导优化方向。对于想深入掌握DP的同学我的建议是多画图多模拟。对于三维问题可以在纸上固定一维画出另外两维的表格手动推导几个状态的值。理解状态之间是如何“流动”的。然后一定要动手实现并尝试用不同的测试用例去“攻击”你的代码思考各种边界情况。像“质数行者”这样的题吃透一道胜过模糊地看十道。