gopackage mainfunc zigZagArrays(n int, l int, r int) int {const MOD int64 1_000_000_007m : r - l 1if 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] 1down[i] 1}// 重复添加 n-1 个元素for step : 1; step n; step {// 前缀和prefixDown[i] sum(down[0..i-1])prefixDown : make([]int64, m1)for i : 0; i m; i {prefixDown[i1] (prefixDown[i] down[i]) % MOD}// 后缀和suffixUp[i] sum(up[i..m-1])suffixUp : make([]int64, m1)for i : m - 1; i 0; i-- {suffixUp[i] (suffixUp[i1] up[i]) % MOD}newUp : make([]int64, m)newDown : make([]int64, m)for x : 0; x m; x {// 上升前一步必须为下降且前一个值 xnewUp[x] prefixDown[x] // sum(down[0..x-1])// 下降前一步必须为上升且前一个值 xnewDown[x] suffixUp[x1] // sum(up[x1..m-1])}up, down newUp, newDown}var total int64for 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)。· 当 n1 时直接返回 m因为任意单元素数组都满足条件。· 所有计算取模 10^97。
