3699. 锯齿形数组的总数 I

原题链接

题目信息

  • 难度：算术评级 8（偏难）
  • 标签：动态规划、前缀和、后缀和、滚动数组
  • 第 469 场周赛 Q3

题目理解

给定 n、l、r，求长度为 n 的锯齿形数组总数。锯齿形数组需要满足：

  1. 每个元素取值 [l, r]
  2. 相邻元素不等
  3. 任意连续三个不能严格递增或严格递减

条件 3 意味着序列的方向必须交替：上升后必须下降，下降后必须上升。这就是经典 zigzag 序列。

思考过程

第一版：暴力 DP（超时 + 超内存）

最直觉的想法：用 dp[i][dir][x] 表示长度为 i、以 x 结尾、下一步方向为 dir 的序列数。

  • dir = 0 → 下一步需要下降（刚刚上升过）
  • dir = 1 → 下一步需要上升（刚刚下降过）

初始化长度为 2 的所有情况（相邻不等即可），然后三重循环向后转移：

for (int x = 0; x < range; x++) {
    for (int y = 0; y < range; y++) {
        if (x != y) {
            if (y > x) dp[2][0][y]++;  // 上升→下一步下降
            else        dp[2][1][y]++;  // 下降→下一步上升
        }
    }
}
for (int i = 2; i < n; i++) {
    for (int y = 0; y < range; y++) {
        for (int x = 0; x < range; x++) {
            if (y < x) dp[i+1][1][y] += dp[i][0][x];
        }
    }
    for (int y = 0; y < range; y++) {
        for (int x = 0; x < range; x++) {
            if (y > x) dp[i+1][0][y] += dp[i][1][x];
        }
    }
}

问题：O(n * range²) 超时，三维 long long 数组超内存。

第二版：前缀和/后缀和优化（通过但不够好）

注意到转移本质是求前缀和和后缀和：

  • dp[i+1][0][y] = sum(dp[i][1][x] for x < y) → 用 前缀和
  • dp[i+1][1][y] = sum(dp[i][0][x] for x > y) → 用 后缀和
for (int i = 2; i < n; ++i) {
    // 前缀和
    vector<int> pre(range, 0);
    long long sum = 0;
    for (int v = 0; v < range; ++v) {
        sum = (sum + dp[i][1][v]) % MOD;
        pre[v] = (int)sum;
    }
    // 后缀和
    vector<int> suf(range, 0);
    sum = 0;
    for (int v = range - 1; v >= 0; --v) {
        sum = (sum + dp[i][0][v]) % MOD;
        suf[v] = (int)sum;
    }
    // 转移
    for (int y = 0; y < range; ++y) {
        if (y > 0) dp[i+1][0][y] = pre[y-1];
        if (y < range-1) dp[i+1][1][y] = suf[y+1];
    }
}

复杂度降到 O(n * range)，但三维 int 数组仍占内存。

第三版：滚动数组 + 单变量前缀和

核心优化：

  1. 滚动数组：只保留 cur 和 nxt 两层，省掉 n 维度
  2. 单变量滚动：不需要 pre/suf 数组，一边遍历一边累加
class Solution {
public:
    const int MOD = 1e9 + 7;
    int zigZagArrays(int n, int l, int r) {
        int range = r - l + 1;
        vector<vector<int>> cur(2, vector<int>(range, 0));

        // 初始化长度为 2
        for (int x = 0; x < range; ++x) {
            for (int y = 0; y < range; ++y) {
                if (x != y) {
                    if (y > x) cur[0][y]++;
                    else        cur[1][y]++;
                }
            }
        }

        for (int i = 2; i < n; ++i) {
            vector<vector<int>> nxt(2, vector<int>(range, 0));

            // 前缀和方向：左→右
            long long preSum = 0;
            for (int y = 0; y < range; ++y) {
                nxt[0][y] = (int)preSum;
                preSum = (preSum + cur[1][y]) % MOD;
            }

            // 后缀和方向：右→左
            long long sufSum = 0;
            for (int y = range - 1; y >= 0; --y) {
                nxt[1][y] = (int)sufSum;
                sufSum = (sufSum + cur[0][y]) % MOD;
            }

            cur.swap(nxt);
        }

        long long ans = 0;
        for (int v = 0; v < range; ++v) {
            ans = (ans + cur[0][v] + cur[1][v]) % MOD;
        }
        return (int)ans;
    }
};

灵神的优化：一维数组 + 奇偶交替

题解链接

把两个方向合并到一个一维数组 f 中，利用奇偶步交替完成方向翻转：

class Solution {
public:
    int zigZagArrays(int n, int l, int r) {
        constexpr int MOD = 1'000'000'007;
        int k = r - l + 1;
        vector<int> f(k, 1);          // 初始长度 1，每个值有 1 种可能

        for (int i = 1; i < n; i++) {
            if (i % 2) {                // 奇数步 → 需要上升
                long long pre = 0;
                for (int j = 0; j < k; j++) {
                    int v = f[j];
                    f[j] = pre % MOD;   // f[j] = 所有小于 j 的和
                    pre += v;
                }
            } else {                    // 偶数步 → 需要下降
                long long suf = 0;
                for (int j = k - 1; j >= 0; j--) {
                    int v = f[j];
                    f[j] = suf % MOD;   // f[j] = 所有大于 j 的和
                    suf += v;
                }
            }
        }

        return reduce(f.begin(), f.end(), 0LL) * 2 % MOD;
    }
};

为什么乘 2？ 我们模拟的是”第一步先上升”的情况，需要补上”第一步先下降”的对称情况。

复杂度分析

版本 时间复杂度 空间复杂度
暴力 DP O(n×k²) O(n×k)
前缀和优化 O(n×k) O(n×k)
滚动数组 O(n×k) O(k)
一维交替 O(n×k) O(k)

（k = r - l + 1 ≤ 2000）

心得总结

这道题对 DP 优化的考验可以说是一层一层剥开的：

  1. 状态定义：dp[i][dir][x] 是最直接的想法，dir 只是标签（区分两种约束），不是用来判断的
  2. 前缀和/后缀和：把内层的 x 循环从 O(k) 降成 O(1)，这是第一次质变
  3. 单变量滚动：不需要额外的 pre/suf 数组，一边遍历一边累加就行，代码更简洁
  4. 一维交替：把两个方向合并到一个数组里，奇偶步交替完成方向翻转，最后乘 2 补偿初始方向——这个设计太优雅了

第四种做法我确实是想不到的，看到答案后也是琢磨了半天才理解为什么乘 2。不过能自己推导到滚动数组版本，也算是对 DP 优化有了更深的理解了吧~

关键教训：状态设计决定了优化的天花板，当你觉得三维 DP 很自然的时候，想想能不能用更巧妙的定义把两个方向合并起来？