3699. Z字形数组I

题目描述

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

长度为 n 的 Z字形数组 定义如下：

• 每个元素都在 [l, r] 范围内。
• 没有两个相邻的元素是相等的。
• 没有三个连续的元素形成严格递增或严格递减的序列。

返回有效Z字形数组的总数。由于答案可能很大，请将其对 $10^9 + 7$ 取模后返回。

如果一个序列中的每个元素都严格大于其前一个元素（如果存在），则称该序列为严格递增。

如果一个序列中的每个元素都严格小于其前一个元素（如果存在），则称该序列为严格递减。

解题思路

题目要求计算长度为 n、元素在 [l, r] 范围内的Z字形数组的数量。约束条件为 $3 \le n \le 2000$ 和 $1 \le l < r \le 2000$。

首先，我们可以通过归一化范围来简化问题。l 和 r 的绝对值不重要，重要的是范围的大小。我们可以将范围 [l, r] 映射到 [1, r - l + 1]。令 m = r - l + 1。

这个问题可以用动态规划来解决。我们需要逐个构建数组元素，同时跟踪必要的信息以满足Z字形条件。我们的DP状态应该编码我们正在填充的当前位置、最后一个元素的值以及最后一次变化的方向（即前一个元素是更小还是更大）。

设 dp[i][j][k] 为长度为 i 的有效Z字形数组的数量，其中第 i 个元素是 j，k 表示最后两个元素之间的关系：

• k = 0：序列在末尾是“向上”的，意味着 A[i-1] < A[i]。下一个元素 A[i+1] 必须小于 A[i]。
• k = 1：序列在末尾是“向下”的，意味着 A[i-1] > A[i]。下一个元素 A[i+1] 必须大于 A[i]。

基本情况: 对于长度为 2 的数组 A[1], A[2]：

• dp[2][j][0] (对于 A[1] < A[2]=j)：A[1] 可以是 1 到 j-1 的任意值。所以有 j-1 种可能性。
• dp[2][j][1] (对于 A[1] > A[2]=j)：A[1] 可以是 j+1 到 m 的任意值。所以有 m-j 种可能性。

状态转移: 对于 i > 2：

• 要计算 dp[i][j][0] (以 ... < j 结尾)，前一个状态必须是 dp[i-1][p][1] 其中 p > j。这确保了Z字形模式（不允许 ... > p < j）。所以，我们需要 A[i-2] > A[i-1] 和 A[i-1] < A[i]。前一个状态必须是向下的。 $dp[i][j][0] = \sum_{p=j+1}^{m} dp[i-1][p][1]$
• 要计算 dp[i][j][1] (以 ... > j 结尾)，前一个状态必须是 dp[i-1][p][0] 其中 p < j。这确保了Z字形模式（不允许 ... < p > j）。所以，我们需要 A[i-2] < A[i-1] 和 A[i-1] > A[i]。前一个状态必须是向上的。 $dp[i][j][1] = \sum_{p=1}^{j-1} dp[i-1][p][0]$

求和过程可以使用前缀和（或者在第一个转移中是后缀和）来优化。对于一个固定的 i，当我们为 j 从 1 到 m 计算 dp[i][j][k] 时，我们可以维护所需 dp[i-1] 值的运行总和。

优化: 我们可以观察到 dp[i] 只依赖于 dp[i-1]。这意味着我们可以通过只使用两个数组来存储当前和前一个长度的DP状态，将空间复杂度从 $O(n \cdot m)$ 优化到 $O(m)$。提供的代码使用了一个三维数组，但逻辑可以用空间优化来实现。

最终答案是所有 dp[n][j][k] 对所有有效的 j 和 k 的总和。

static const auto fast_io = []() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();
#define N 2005
class Solution {
public:
    int mod = 1e9 + 7;
    int dp[N][N][2];
    int zigZagArrays(int n, int l, int r) {
        r -= l;
        r++;
        l = 1;
        int ans = 0;
        // 0 next need incresing, 1 next need to descring
        for (int i = 1; i < r + 1; i++) {
            dp[2][i][0] = r - i;
            dp[2][i][1] = i - 1;
        }
        for (int i = 3; i <= n; i++) {
            int tmp1 = 0;
            for (int j = 1; j < r + 1; j++) {
                dp[i][j][1] = tmp1;
                tmp1 += dp[i - 1][j][0];
                dp[i][j][1] %= mod;
                tmp1 %= mod;
            }
            tmp1 = 0;
            for (int j = r; j >= 1; j--) {
                dp[i][j][0] = tmp1;
                tmp1 += dp[i - 1][j][1];
                dp[i][j][0] %= mod;
                tmp1 %= mod;
            }
        }

        // sum of dp[n][all j][all k]
        for (int i = 1; i < r + 1; i++) {
            ans += dp[n][i][0];
            ans %= mod;
            ans += dp[n][i][1];
            ans %= mod;
        }
        return ans;
    }
};

时间和空间复杂度

• 时间复杂度: $O(n \cdot (r-l))$。我们迭代 n 次，对于每个 i，我们遍历所有 m = r-l+1 个可能的值。
• 空间复杂度: $O(n \cdot (r-l))$ 用于DP表。由于 dp[i] 只依赖于 dp[i-1]，这可以优化到 $O(r-l)$。