T3699.锯齿形数组的总数 I

https://leetcode.cn/problems/number-of-zigzag-arrays-i/

给你三个整数 n、l 和 r。

长度为 n 的锯齿形数组定义如下：

每个元素的取值范围为 [l, r]。
任意两个相邻的元素都不相等。
任意三个连续的元素不能构成一个 严格递增 或 严格递减 的序列。

返回满足条件的锯齿形数组的总数。

由于答案可能很大，请将结果对 109 + 7 取余数。

序列被称为 严格递增 需要满足：当且仅当每个元素都严格大于它的前一个元素（如果存在）。

序列被称为 严格递减 需要满足，当且仅当每个元素都严格小于它的前一个元素（如果存在）。

示例 1：

输入：n = 3, l = 4, r = 5

输出：2

解释：

在取值范围 [4, 5] 内，长度为 n = 3 的锯齿形数组只有 2 种：

[4, 5, 4]
[5, 4, 5]

示例 2：

输入：n = 3, l = 1, r = 3

输出：10

解释：

在取值范围 [1, 3] 内，长度为 n = 3 的锯齿形数组共有 10 种：

[1, 2, 1], [1, 3, 1], [1, 3, 2]
[2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2]
[3, 1, 2], [3, 1, 3], [3, 2, 3]

所有数组均符合锯齿形条件。

提示：

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

这是一个可以使用动态规划（Dynamic Programming）来解决的问题。

解题思路

为了满足条件：

每个元素的取值范围在 $[l, r]$ 。为了方便计算，我们将这些数映射到 $[0, M - 1]$ 的区间，其中 $M = r - l + 1$ 。
相邻元素不相等。
连续三个元素不能单调递增或单调递减。这意味着如果前一次状态是“上升”的（即 $a_{i - 2} < a_{i - 1}$ ），下一次状态必须是“下降”的（即 $a_{i - 1} > a_{i}$ ）；反之亦然。

我们可以定义状态来记录当前数组的长度、最后一个元素的值，以及上一步是“上升”还是“下降”。设：

dp0[v] 表示长度为 $i$ 且以值 $v$ 结尾，且最后一步是下降（即前一个元素大于 $v$ ）的合法数组数量。
dp1[v] 表示长度为 $i$ 且以值 $v$ 结尾，且最后一步是上升（即前一个元素小于 $v$ ）的合法数组数量。

1. 边界情况（长度为 2 时）

对于长度为 2 的数组 $a_{0}, a_{1}$ ：

若最后一步是下降，即 $a_{0} > a_{1} = v$ ，则 $a_{0}$ 可以取 $[v + 1, M - 1]$ 中的任意值。此时共有 $(M - 1 - v)$ 种选择。
若最后一步是上升，即 $a_{0} < a_{1} = v$ ，则 $a_{0}$ 可以取 $[0, v - 1]$ 中的任意值。此时共有 $v$ 种选择。

2. 状态转移

当长度从 $i - 1$ 增加到 $i$ 时：

如果当前步是下降（到达 $v$ ），那么前一步必须是上升（到达 $u$ 且 $u > v$ ）： $d p 0_{n e w} [v] = \sum_{u = v + 1}^{M - 1} d p 1 [u]$
如果当前步是上升（到达 $v$ ），那么前一步必须是下降（到达 $u$ 且 $u < v$ ）： $d p 1_{n e w} [v] = \sum_{u = 0}^{v - 1} d p 0 [u]$

如果直接计算上述转移，每次转移需要 $O (M)$ 的时间，总时间复杂度为 $O (n \cdot M^{2})$ 。当 $n, M \leq 2000$ 时会超时。我们可以通过维护 dp0 的前缀和以及 dp1 的后缀和，将状态转移优化到 $O (1)$ ，从而使总时间复杂度降至 $O (n \cdot M)$ 。

Python 代码

python

class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        MOD = 1_000_000_007
        M = r - l + 1
        
        if M < 2:
            return 0  # 相邻元素不能相等，若只有一个可选值则无法构造
            
        # dp0[v]: 最后一个元素是 v，且最后一步是“下降” (即前一个元素 > v)
        # dp1[v]: 最后一个元素是 v，且最后一步是“上升” (即前一个元素 < v)
        dp0 = [M - 1 - v for v in range(M)]
        dp1 = [v for v in range(M)]
        
        for _ in range(3, n + 1):
            # 计算 dp0 的前缀和，用于快速计算 sum(dp0[u] for u < v)
            pref0 = [0] * M
            s = 0
            for v in range(M):
                s = (s + dp0[v]) % MOD
                pref0[v] = s
                
            # 计算 dp1 的后缀和，用于快速计算 sum(dp1[u] for u > v)
            suff1 = [0] * M
            s = 0
            for v in range(M - 1, -1, -1):
                s = (s + dp1[v]) % MOD
                suff1[v] = s
                
            next_dp0 = [0] * M
            next_dp1 = [0] * M
            for v in range(M):
                # 这一步下降到 v，前一步必须是从更高级别的 u 上升到 u 
                if v + 1 < M:
                    next_dp0[v] = suff1[v + 1]
                # 这一步上升到 v，前一步必须是从更低级别的 u 下降到 u
                if v - 1 >= 0:
                    next_dp1[v] = pref0[v - 1]
                    
            dp0 = next_dp0
            dp1 = next_dp1
            
        return (sum(dp0) + sum(dp1)) % MOD

复杂度分析

时间复杂度： $O (n \cdot M)$ ，其中 $M = r - l + 1$ 。每次循环我们进行常数次大小为 $M$ 的线性扫描。在最坏情况下（ $n = 2000, M = 2000$ ），计算量约为 $4 \times 10^{6}$ 次操作，运行时间在 0.1 秒左右。
空间复杂度： $O (M)$ 。我们只维护当前步和上一步的状态数组，因此空间复杂度与 $n$ 无关，仅取决于可选数值的数量。

T3699.锯齿形数组的总数 I ​

T3699.锯齿形数组的总数 I