企业官网建设流程全解析

练动态规划题的时候，有一类题特别容易让人“一开始觉得是排列组合，写着写着发现是 DP，最后 AC 了也不知道为什么对”，蓝桥杯模拟赛里的「摆动序列」就是这样一道题。它考的并不是花哨的算法，而是最朴素也最容易出错的计数 DP：状态怎么定义、方向怎么保留、前缀和怎么优化。如果你正准备蓝桥杯省赛，或者想系统练一下动态规划的计数模型，这道题值得认真做一遍。

1. 摆动序列这道题，到底在数什么

先统一一下题目背景。题目会给你两个整数，一个代表序列长度，一个代表数字的取值范围上限。要求统计满足摆动性质的序列个数，结果对某个模数取余（蓝桥很多版本要求对 10000 取模）。

什么叫“摆动”？最常见的定义是：从第 2 个数开始，相邻两个数的比较关系必须是“小于、大于、小于、大于……”这样交替，不允许连续两个方向相同。换句话说，序列的山谷和山峰要交替出现。

比如1 3 2 4，3 和 2 的关系是先上升再下降，2 和 4 是下降后再上升，方向分别是“升、降、升”，满足交替。而1 2 3 4的方向是“升、升、升”，连续同向，不摆动。4 3 2 1也不摆动，因为连续下降。

这里有一个常见理解误区：摆动序列不是要求“必须一会儿上一会儿下”那么简单，而是要每一步的相对大小方向都与上一步相反。所以看一个序列是否符合，不要只盯着局部两个数看，要连续看三次比较结果。

很多同学第一反应是 DFS 枚举或者全排列暴力判断。范围小的时候当然能过，比如长度不超过 8、数值不超过 8，手写个 dfs 没问题。但蓝桥的这道题数据再温和也不会这么小，省赛模拟通常会把 n 和 m 放到 1000 级别，此时全排列数量是 m^n 级别，暴力必然超时。

所以这道题的正解必须用动态规划。动态规划在这里解决的本质问题是：在不枚举整条序列的情况下，用“上一次的最后状态”去承接“下一次的扩展”。而摆动序列的“上一次状态”必须同时包含两个信息：最后一个数字是谁、最后一次比较的方向是什么。这一点会直接引出我们要用的 DP 状态设计。

另外提醒一句：输入顺序在不同题解里写得不一致。有的题目写“第一行 n，第二行 m”，有的写“n m 在同一行”，还有的会把 n 和 m 的含义反过来。我的建议是拿到题先看样例，确定哪个是长度、哪个是数值上限。本文统一用n表示序列长度，m表示数字取值范围 1 到 m。

2. 状态设计：只记“当前数字”远远不够

我第一次做这道题时，很自然想到dp[i][j]：长度为 i、最后一个数字是 j 的摆动序列个数。结果一写就发现转移没法保证方向交替。原因很简单：序列1 2的长度为 2、最后一个是 2，和序列3 2的长度为 2、最后一个是 2，两者虽然都落在同一个状态里，但前一个是上升到达 2 的，后一个是下降到达 2 的。如果继续向长度 3 扩展，对前一个序列，下一步必须下降；对后一个序列，下一步必须上升。把它们混在一个状态里，就丢掉了关键信息。

所以必须把“最后一步的方向”也装进状态里。我使用两个 DP 表：

• up[i][j]：长度为 i，最后一个数字是 j，且最后一步是“上升”到达 j 的摆动序列个数。
• down[i][j]：长度为 i，最后一个数字是 j，且最后一步是“下降”到达 j 的摆动序列个数。

“最后一步上升”意思是序列中倒数第二个数小于 j；“最后一步下降”意思是倒数第二个数大于 j。

转移的时候要交叉，因为方向必须交替：

• 要得到up[i][j]，上一步必须是下降。也就是倒数第二个数 t 必须满足 t < j，同时上一步状态是下降。所以：up[i][j] = sum(down[i-1][t])，其中 1 <= t < j

• 要得到down[i][j]，上一步必须是上升。也就是倒数第二个数 t 必须满足 t > j，同时上一步状态是上升。所以：down[i][j] = sum(up[i-1][t])，其中 j < t <= m

初始化从长度为 2 开始。长度为 1 时没有所谓“最后一步方向”，不适合直接放进 up 或 down。长度 2 的状态数是显式的：

• up[2][j] = j - 1，因为倒数第一个数可以是 1 到 j-1 中的任意一个，且最后一步都是上升。
• down[2][j] = m - j，因为倒数第一个数可以是 j+1 到 m 中的任意一个，且最后一步都是下降。

有了这个初始化，长度 3 及以上的转移就能直接用交叉公式滚动下去。

我拿m=4，n=3来验证一组中间结果。长度 2 初始化之后：

up[2] [0, 1, 2, 3] （下标从 1 开始，下同） down[2] [3, 2, 1, 0]

计算长度 3：

• up[3][2] = down[2][1] = 3，对应序列最后一步上升且末尾是 2。
• up[3][3] = down[2][1] + down[2][2] = 3 + 2 = 5。
• down[3][1] = up[2][2] + up[2][3] + up[2][4] = 1 + 2 + 3 = 6。

全部算完，up[3] = [0, 3, 5, 6]，down[3] = [6, 5, 3, 0]，加起来是0+3+5+6+6+5+3+0 = 28。

这个 28 可以用一个小公式交叉验证。长度为 3 的摆动序列只有两种模式：先升后降、先降后升。先升后降时，中间数字取 b，那么两端的数都必须在 1 到 b-1 中选，因此数量是(b-1)^2；先降后升时，两端数都在 b+1 到 m 中选，数量是(m-b)^2。对 b 从 1 到 m 求和，也就是：

sum((b-1)^2 + (m-b)^2)

代入 m=4：(0+9) + (1+4) + (4+1) + (9+0) = 28，和 DP 结果一模一样。这样核对过，基本可以确定状态和转移没有写歪。

3. 三重循环为什么要放弃：前缀和把 O(nm^2) 降到 O(nm)

如果直接按照转移公式写，代码会是一个三层循环：

for (int i = 3; i <= n; i++) { for (int j = 1; j <= m; j++) { for (int t = 1; t < j; t++) { up[i][j] = (up[i][j] + down[i-1][t]) % MOD; } for (int t = j + 1; t <= m; t++) { down[i][j] = (down[i][j] + up[i-1][t]) % MOD; } } }

这个写法的好处是直观，和转移方程完全对应。但复杂度是O(n*m^2)。当 n 和 m 都到 1000 时，计算量大约是 10^9 级别，在蓝桥杯的时限下很容易超时；如果 n 和 m 到 2000，更是完全不能接受。

优化的突破口在于：我们其实是在反复求一个连续区间的和。

up[i][j]要求的是down[i-1][1] + down[i-1][2] + ... + down[i-1][j-1]。这是down[i-1]的一个前缀和。down[i][j]要求的是up[i-1][j+1] + up[i-1][j+2] + ... + up[i-1][m]。这是up[i-1]的一个后缀和。

同一个 i-1 层的前缀和后缀和，可以在每个长度 i 只扫两遍数组算出来。从左到右扫一遍，维护pre，表示已经扫过的down[i-1]的累加和；从右到左扫一遍，维护suf，表示已经扫过的up[i-1]的累加和。这样每个状态的计算变成 O(1)，总复杂度降到O(n*m)。

具体来说，计算第 i 层时，先从左往右计算up[i][j]：

int pre = 0; for (int j = 1; j <= m; j++) { up[i][j] = pre; pre = (pre + down[i-1][j]) % MOD; }

这里要注意顺序：先用pre赋值，再把down[i-1][j]累加进pre。赋值在前，所以up[i][j]只包含序号小于 j 的那些元素，不会把自己算进去。

再从右往左计算down[i][j]：

int suf = 0; for (int j = m; j >= 1; j--) { down[i][j] = suf; suf = (suf + up[i-1][j]) % MOD; }

同理，赋值在前，累加在后，down[i][j]只包含序号大于 j 的那些元素。

如果不小心把顺序写反，就会把down[i-1][j]自己也算进up[i][j]里，等价于允许最后一步“原地踏步”，这会导致答案偏大。这是我实测最容易翻车的细节，后面避坑部分会再强调。

做完了这一层优化，如果你继续往下想，会意识到其实连第 i 层整层的二维数组都不用保留。转移时只用了 i-1 层的数据，所以我们完全可以用滚动数组：当前层算完后，把当前层覆盖到上一层，继续算下一层。空间从O(n*m)降成O(m)。

滚动的写法有一个小坑：不要在一个数组里同时边读边写。建议准备up/down存上一层，nxtUp/nxtDown存当前层，当前层算完后再整体替换。这样逻辑清晰，也避免下一秒发现 up[j] 已经被覆盖成新值而出错。

4. 可直接提交的 C++/Python 代码与自测

下面给出完整代码。默认读入格式是：第一个数 n 表示序列长度，第二个数 m 表示数字范围上限。如果你遇到的是相反顺序，把两个变量的读取调换即可。

C++ 代码，滚动数组 + 前缀和：

#include <bits/stdc++.h> using namespace std; const int MOD = 10000; int main() { int n, m; cin >> n >> m; // 原题要求至少两个数，长度为 1 时没有合法序列 if (n == 1) { cout << 0 << "\n"; return 0; } vector<int> up(m + 1, 0), down(m + 1, 0); // 长度为 2 的初值 for (int j = 1; j <= m; j++) { up[j] = j - 1; // 上一个数小于 j down[j] = m - j; // 上一个数大于 j } if (n == 2) { long long ans = 0; for (int j = 1; j <= m; j++) { ans += up[j] + down[j]; } cout << ans % MOD << "\n"; return 0; } vector<int> nxtUp(m + 1, 0), nxtDown(m + 1, 0); for (int len = 3; len <= n; len++) { // up[len][j] = sum(down[len-1][1..j-1]) int pre = 0; for (int j = 1; j <= m; j++) { nxtUp[j] = pre; pre = (pre + down[j]) % MOD; } // down[len][j] = sum(up[len-1][j+1..m]) int suf = 0; for (int j = m; j >= 1; j--) { nxtDown[j] = suf; suf = (suf + up[j]) % MOD; } up.swap(nxtUp); down.swap(nxtDown); } int ans = 0; for (int j = 1; j <= m; j++) { ans = (ans + up[j] + down[j]) % MOD; } cout << ans << "\n"; return 0; }

Python 代码，逻辑相同：

MOD = 10000 def solve(): n, m = map(int, input().split()) if n == 1: print(0) return up = [0] * (m + 1) down = [0] * (m + 1) for j in range(1, m + 1): up[j] = j - 1 down[j] = m - j if n == 2: print((sum(up[1:] + down[1:])) % MOD) return for _ in range(3, n + 1): nxt_up = [0] * (m + 1) nxt_down = [0] * (m + 1) pre = 0 for j in range(1, m + 1): nxt_up[j] = pre pre = (pre + down[j]) % MOD suf = 0 for j in range(m, 0, -1): nxt_down[j] = suf suf = (suf + up[j]) % MOD up, down = nxt_up, nxt_down print((sum(up[1:] + down[1:])) % MOD) if __name__ == "__main__": solve()

几个自测样例：

第四个样例特别容易被忽略。如果题目有“至少两个数”的条件，长度为 1 时应该输出 0；如果某个版本把长度为 1 也算作摆动序列，那才需要考虑输出 m。做题时务必看题面怎么说。

5. 实战中容易翻车的细节清单

这道题看起来短，能一次写对的人其实不多。下面这些坑，我基本都踩过，或者帮别人 debug 时见过。

第一，输入顺序和含义搞错。很多同学把 n 和 m 交换了还浑然不觉，最后样例都过不了。建议拿到题先做一个小样例手动算，比如n=2, m=3，长度为 2 的合法序列应该是3*2=6，输入后如果输出不是 6，说明读反了。

第二，长度 2 初始化和长度 1 的处理。up[2][j] = j-1、down[2][j] = m-j这两个式子里，如果写成了j或者m-j+1，就会把“数字相同，原地不动”的情况也算进去。比如1 1这类相邻相等序列会被误判为合法。正因如此，我建议你初始化时先打印一下表，m=4时 up 和 down 加起来每列都应该是 3，也就是总共 12 个长度为 2 的序列。

第三，前缀和赋值顺序写反。我在前面已经反复强调：一定是“先赋值，再累加”。如果写成：

pre = (pre + down[j]) % MOD; nxtUp[j] = pre;

那nxtUp[j]就把 j 自己算进去了，最后一步等于没动，方向消失。这个 bug 在手工验证小数据时就会暴露：n=3, m=4时答案会从 28 变成 36。36 正好是所有相邻不相等三元序列的数量，说明已经退化成“只要求相邻不同、不要求方向交替”了，完全违背题意。

第四，取模的位置。蓝桥要求答案对 10000 取模，但转移过程中的 pre 和 suf 也要及时取模。不取模的话，n 和 m 到 1000 时，答案会膨胀得非常快，long long 都不一定扛得住。不过这里的取模并不会影响后续状态计算，因为加法取模满足结合律，每一层都保留余数就够了。

第五，关于“序列中的数两两不同”这个流传版本。网上很多地方把这句话也放进题面里。但根据我看到的多数模拟赛和题解，数据范围通常会到 1000，如果真的要保证“全局每个数字不重复”，状态里必须记录哪些数字用过了，复杂度和状态数都会爆炸，基本不可能用普通 DP 完成。真正遇到“两两不同”的小数据版本，可以用状态压缩 DP：dp[mask][j][0/1]表示已使用数字集合为 mask、最后一个是 j、最后方向是升或者降的序列数，逐位扩展即可。如果题面同时给了 n、m 到 1000 的数据范围，那大概率评测数据并不会对非相邻重复做限制，使用本文的双状态 DP 就是预期解法。做题时以本地样例和评测结果为准。

第六，滚动数组的清理。用swap之前，要保证nxtUp和nxtDown已被完整覆盖。如果某轮循环只覆盖了下标 1 到 m 的局部，另一部分残留了旧值，最后求和时就会把垃圾数据加进去。稳妥做法是每一轮都先fill清零，或者像上面的代码一样，从 1 到 m 完整赋值，确保不存在残留。

6. 从这道题提炼的 DP 通用套路

摆动序列这道题，本质上是“带方向的计数 DP”。它给我们的第一个启示是：当转移条件依赖“上一步做了什么”时，不要犹豫，把这个动作直接设计成状态维度。很多同学习惯只关注“当前数字”，结果一旦下一个转移需要对方向做判断，就开始在转移里猜历史，最后写出一堆特判。正确做法是提早把方向拆成两个数组，或者用一个维度 0/1 表示方向。

第二个启示是：区间求和型转移，优先想到前缀和。up[i][j] = sum(down[i-1][1..j-1])这种式子，一眼就能看出可以用前缀和优化。如果你在转移里看到for t in range(...) sum，先别急着写三重循环，停下来想想能不能维护一个滚动累加变量。这个方法在最长上升子序列、最大子段和相关 DP 里同样适用。

第三个启示是：边界条件要单独列出来。长度为 1 和长度为 2 在摆动序列里的定义天然不同，很多入门 DP 题也是栽在边界上。写代码前，先把边界情况在纸上列清楚：哪些长度没有方向、哪些状态可以直接给初值、哪些长度需要走转移循环。

第四个启示是：验证小数据时，可以找一个独立公式交叉验证。比如这道题长度为 3 时，我用sum((b-1)^2 + (m-b)^2)去核对 DP 结果。这样做的好处是，一旦 DP 初始化或转移有偏差，立刻能发现，而不是等提交后 WA 了再慢慢调。以后做任何计数 DP，都可以这样设计一个小规模的“独立算法”来对拍，哪怕只是手写几个简单的枚举。

这一题做完再回头看，它的难度其实不在转移方程本身，而在“方向”这个维度的取舍，以及前缀和优化的敏感性。如果你能不看题解一次性把这两种优化都写对，那蓝桥杯里绝大多数计数型动态规划题，对你来说只是数据范围的问题了。