输入#

三个整数 n、l、r

输出#

满足条件的锯齿形数组总数（对 $10^9 + 7$ 取余）

约束条件#

1. 3 <= n <= 2000
2. 1 <= l < r <= 2000

示例1#

1
input: n = 3, l = 4, r = 5
2
output: 2

解释：取值范围 [4, 5] 内，长度为 3 的锯齿形数组只有 [4, 5, 4] 和 [5, 4, 5] 两种。

示例2#

1
input: n = 3, l = 1, r = 3
2
output: 10

解释：取值范围 [1, 3] 内，长度为 3 的锯齿形数组共有 10 种，例如 [1, 2, 1]、[2, 1, 3]、[3, 2, 3] 等，均满足锯齿形条件。

从直观做法出发#

最容易想到的是：逐位填数，每填一个新元素时检查「是否与前一数不同」以及「最近三个数是否单调」。这是标准的 DFS / 回溯思路，但状态空间约为 $O(k^n)$（$k = r - l + 1$），在 $n = 2000$ 时完全无法接受。

换一个角度：锯齿形的核心约束其实落在相邻两数的大小关系上——

• 「相邻不等」要求 $a_i \neq a_{i+1}$；
• 「不能有三连单调」等价于：不能连续两步同向变化，即不能出现 $a_{i-1} < a_i < a_{i+1}$（三连增）或 $a_{i-1} > a_i > a_{i+1}$（三连减）。

因此，只要知道最后两个数的大小关系（递增还是递减），就能判断下一个数该往哪边放，而无需记录更长的历史。

定义 DP 状态#

将取值 [l, r] 映射为相对下标 0, 1, …, k-1（$k = r - l + 1$），定义：

• f0[i][j]：长度为 i、第 i 个数为 l + j，且最后两个数严格递增的方案数；
• f1[i][j]：长度为 i、第 i 个数为 l + j，且最后两个数严格递减的方案数。

长度为 1 的数组还没有「最后两个数」，初始化时每个取值各 1 种方案。

推导转移方程#

要从长度 i - 1 扩展到长度 i，在位置 j 填上新元素 l + j：

转移到 f0[i][j]（末尾递增，即 $a_{i-1} < a_i$）

上一个状态必须是「末尾递减」的 f1[i-1][k]，且要求 $l + k < l + j$，即 $k < j$：

$f0[i][j] = \sum_{k=0}^{j-1} f1[i-1][k]$

转移到 f1[i][j]（末尾递减，即 $a_{i-1} > a_i$）

上一个状态必须是「末尾递增」的 f0[i-1][k]，且要求 $l + k > l + j$，即 $k > j$：

$f1[i][j] = \sum_{k=j+1}^{k-1} f0[i-1][k]$

直接双重循环转移是 $O(k^2)$ 每层，总复杂度 $O(n \cdot k^2)$，在 $n, k \le 2000$ 时会超时。观察转移式：一个是前缀和，一个是后缀和。

前缀和 / 后缀和加速#

对 f1[i-1] 做前缀和 pre，则 $f0[i][j] = pre[j-1]$（$j = 0$ 时为 0）。

对 f0[i-1] 做后缀和 suf，则 $f1[i][j] = suf[j+1]$（$j = k-1$ 时为 0）。

每层更新降为 $O(k)$，总时间 $O(n \cdot k)$。

滚动数组：一层交替更新#

f0 和 f1 交替依赖，可以用同一个数组原地滚动：

• 偶数轮（u % 2 == 0）：当前数组视为 f0，做后缀和得到新的 f1；
• 奇数轮（u % 2 == 1）：当前数组视为 f1，做前缀和得到新的 f0。

以 n = 3, l = 4, r = 5（$k = 2$）为例：

sum(f) = 1，最终答案 1 × 2 = 2，与示例一致。

为何最后乘以 2#

经过 n - 1 轮转移后，数组里只保留了一种末尾方向的状态（n 为奇数时对应 f0，n 为偶数时对应 f1）。

但合法的锯齿形数组在结尾处可以是「末尾递增」或「末尾递减」两种，且由于前缀和与后缀和的对称性，两种方向的方案总数相等：

$\sum_j f0[n][j] = \sum_j f1[n][j]$

因此最终答案为 sum(f) * 2。

复杂度#

• 时间复杂度：$O(n \cdot k)$，其中 $k = r - l + 1$
• 空间复杂度：$O(k)$，只维护一个滚动数组

代码#

1
class Solution:
2
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
3
        """
4
        f0[i][j]: 包含 i 个数，第 i 个数是 j，且后两个数递增的方案数
5
        f1[i][j]: 包含 i 个数，第 i 个数是 j，且后两个数递减的方案数
6

7
        f0[i][j] = sum(f1[i - 1][k], k in [0, j - 1])
8
        f1[i][j] = sum(f0[i - 1][k], k in [j + 1, k - 1])
9
        """
10
        mod = 1_000_000_007
11
        k = r - l + 1
12
        f = [1] * k
13

14
        for u in range(n - 1):
15
            if u % 2:
16
                pre = 0
17
                for i, v in enumerate(f):
18
                    f[i] = pre % mod
19
                    pre += v
20
            else:
21
                suf = 0
22
                for i in range(k - 1, -1, -1):
23
                    v = f[i]
24
                    f[i] = suf % mod
25
                    suf += v
26

27
        return sum(f) * 2 % mod

状态的另一种含义#

定义 dp[i][dir][x]：长度为 i、以值 x 结尾、且下一个元素相对 x 必须：

• dir = 1（上升）：下一个数 $> x$；
• dir = 0（下降）：下一个数 $< x$。

这与上一节的对应关系为：

「不能三连单调」正是强制方向交替：每次填数后，下一步的方向与上一步相反。

转移（与官方提示一致）#

若当前要求上升（dir = 1），可从所有「上一步要求下降、且值小于 y」的状态转移而来：

$dp[i+1][0][y] \mathrel{+}= \sum_{x < y} dp[i][1][x]$

若当前要求下降（dir = 0），则从所有「上一步要求上升、且值大于 y」的状态转移：

$dp[i+1][1][y] \mathrel{+}= \sum_{x > y} dp[i][0][x]$

这与上一节的 f0 / f1 转移完全等价，同样可用前缀和 / 后缀和优化到 $O(n \cdot k)$。

何时需要显式维护 dir#

当题目要求输出以特定方向结尾的方案数，或需要区分「第一个元素比第二个大 / 小」时，应同时维护 dp[i][0] 和 dp[i][1] 两个数组，而不能在结尾用 × 2 合并。

本题只统计总数，且两种结尾方向的方案数对称相等，故压缩为一个滚动数组并在最后 × 2 是合理的。

显式维护 f0 / f1，避免 ×2 技巧#

将两种末尾方向拆成两个数组，逻辑更直白，也省去结尾 × 2 的对称性说明：

1
class Solution:
2
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
3
        mod = 1_000_000_007
4
        k = r - l + 1
5
        f0 = f1 = [1] * k  # 长度 1 时两种方向尚未区分，各自为 1
6

7
        for _ in range(n - 1):
8
            # f0[i][j] = prefix_sum(f1[i-1])[j]
9
            pre = 0
10
            new_f0 = [0] * k
11
            for j in range(k):
12
                new_f0[j] = pre % mod
13
                pre = (pre + f1[j]) % mod
14

15
            # f1[i][j] = suffix_sum(f0[i-1])[j]
16
            suf = 0
17
            new_f1 = [0] * k
18
            for j in range(k - 1, -1, -1):
19
                new_f1[j] = suf % mod
20
                suf = (suf + f0[j]) % mod
21

22
            f0, f1 = new_f0, new_f1
23

24
        return (sum(f0) + sum(f1)) % mod

注意：长度 1 时 f0 与 f1 同为 [1,…,1] 会在第一次转移时各自统计到所有合法的长度 2 序列，不会重复计数。渐近复杂度不变，空间为 $O(k)$（两个数组可进一步优化为交替复用）。

抽取前缀 / 后缀更新为内联循环#

原实现用 u % 2 在两种更新间切换，极为紧凑。若更在意可读性，可将「前缀和原地变换」和「后缀和原地变换」写成两个独立的小循环，避免读者反复推断奇偶轮的含义：

1
def to_prefix(f: list[int], mod: int) -> None:
2
    pre = 0
3
    for i, v in enumerate(f):
4
        f[i] = pre % mod
5
        pre = (pre + v) % mod
6

7
def to_suffix(f: list[int], mod: int) -> None:
8
    suf = 0
9
    for i in range(len(f) - 1, -1, -1):
10
        v = f[i]
11
        f[i] = suf % mod
12
        suf = (suf + v) % mod

主循环中按轮次调用 to_suffix / to_prefix 即可，行为与原代码完全一致。

小结#

本题 $n, k \le 2000$，三种写法的时间均为 $O(n \cdot k)$，空间均为 $O(k)$，性能差距极小。日常刷题推荐原版的单数组写法；若需要向他人讲解，双数组版本更易于逐步验证。