企业官网建设流程全解析

```go
package main

func zigZagArrays(n int, l int, r int) int {
const MOD int64 = 1_000_000_007
m := r - l + 1
if n == 1 {
return m
}

// up[i]: 以值 i 结尾，且最后一步为上升的方案数
// down[i]: 以值 i 结尾，且最后一步为下降的方案数
up := make([]int64, m)
down := make([]int64, m)
for i := 0; i < m; i++ {
up[i] = 1
down[i] = 1
}

// 重复添加 n-1 个元素
for step := 1; step < n; step++ {
// 前缀和：prefixDown[i] = sum(down[0..i-1])
prefixDown := make([]int64, m+1)
for i := 0; i < m; i++ {
prefixDown[i+1] = (prefixDown[i] + down[i]) % MOD
}
// 后缀和：suffixUp[i] = sum(up[i..m-1])
suffixUp := make([]int64, m+1)
for i := m - 1; i >= 0; i-- {
suffixUp[i] = (suffixUp[i+1] + up[i]) % MOD
}

newUp := make([]int64, m)
newDown := make([]int64, m)
for x := 0; x < m; x++ {
// 上升：前一步必须为下降，且前一个值 < x
newUp[x] = prefixDown[x] // sum(down[0..x-1])
// 下降：前一步必须为上升，且前一个值 > x
newDown[x] = suffixUp[x+1] // sum(up[x+1..m-1])
}
up, down = newUp, newDown
}

var total int64
for i := 0; i < m; i++ {
total = (total + up[i] + down[i]) % MOD
}
return int(total)
}
```

复杂度分析

· 时间复杂度：O(n \cdot m)，其中 m = r - l + 1。
· 空间复杂度：O(m)。

关键点

· 用 up 和 down 分别表示最后一步方向为上升/下降的方案数。
· 使用前缀和和后缀和将状态转移优化为 O(m)，整体 O(n \cdot m)。
· 当 n=1 时直接返回 m，因为任意单元素数组都满足条件。
· 所有计算取模 10^9+7。