这道题的核心是动态规划 + 前缀和优化。因为数组的增减趋势必须交替（如 a<b>c<d），我们只需记录最后一个值和最后一步方向。

核心思路

· 状态定义：up[i] 表示最后一步为上升且以值 i 结尾的方案数；down[i] 同理为下降。
· 状态转移：
  · 要形成新的上升（到 x），前一步必须是下降且结尾值 < x：newUp[x] = sum(down[0] + ... + down[x-1])。
  · 要形成新的下降（到 x），前一步必须是上升且结尾值 > x：newDown[x] = sum(up[x+1] + ... + up[m-1])。
· 优化：用前缀和快速计算 newUp，用后缀和快速计算 newDown，避免遍历求和，将复杂度从 O(n·m²) 降至 O(n·m)。

---

Java 实现（空间优化版 O(m)）

```java
class Solution {
    private static final int MOD = 1_000_000_007;

    public int zigZagArrays(int n, int l, int r) {
        int m = r - l + 1; // 取值个数
        
        // 初始化长度为 1 的情况：每个值都可以作为起点
        long[] up = new long[m];
        long[] down = new long[m];
        for (int i = 0; i < m; i++) {
            up[i] = 1;
            down[i] = 1;
        }

        // 重复 n-1 次，每次在末尾添加一个数
        for (int len = 2; len <= n; len++) {
            long[] newUp = new long[m];
            long[] newDown = new long[m];

            // 计算前缀和（用于 newUp）
            long prefixSum = 0;
            for (int x = 0; x < m; x++) {
                newUp[x] = prefixSum; // sum of down[0..x-1]
                prefixSum = (prefixSum + down[x]) % MOD;
            }

            // 计算后缀和（用于 newDown）
            long suffixSum = 0;
            for (int x = m - 1; x >= 0; x--) {
                newDown[x] = suffixSum; // sum of up[x+1..m-1]
                suffixSum = (suffixSum + up[x]) % MOD;
            }

            up = newUp;
            down = newDown;
        }

        // 答案：所有 up 和 down 之和
        long ans = 0;
        for (int i = 0; i < m; i++) {
            ans = (ans + up[i] + down[i]) % MOD;
        }
        return (int) ans;
    }
}
```

另一种写法（滚动数组 + 前缀和数组）

使用 prefixSums 和 suffixSums 辅助计算：

```java
class Solution {
    private static final int MOD = 1_000_000_007;

    public int zigZagArrays(int n, int l, int r) {
        int m = r - l + 1;
        int[] up = new int[m];
        int[] down = new int[m];
        int[] prefixUp = new int[m + 1];
        int[] prefixDown = new int[m + 1];

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

        for (int i = 1; i < n; i++) {
            int[] newUp = new int[m];
            int[] newDown = new int[m];
            int[] newPrefixUp = new int[m + 1];
            int[] newPrefixDown = new int[m + 1];

            for (int j = 0; j < m; j++) {
                // 上升：前一步下降且值 < j
                newUp[j] = (j > 0) ? prefixDown[j] : 0; // prefixDown[j] = sum(down[0..j-1])
                // 下降：前一步上升且值 > j
                newDown[j] = (j + 1 < m) ? (prefixUp[m] - prefixUp[j + 1] + MOD) % MOD : 0;

                newPrefixUp[j + 1] = (newPrefixUp[j] + newUp[j]) % MOD;
                newPrefixDown[j + 1] = (newPrefixDown[j] + newDown[j]) % MOD;
            }

            up = newUp;
            down = newDown;
            prefixUp = newPrefixUp;
            prefixDown = newPrefixDown;
        }

        return (prefixUp[m] + prefixDown[m]) % MOD;
    }
}
```

复杂度

· 时间复杂度：O(n·m)
· 空间复杂度：O(m)