DeepSeek LeetCode 3699. 锯齿形数组的总数 I Python3实现

这个问题要求计算长度为 n、元素值在 [l, r] 之间的“锯齿形”数组的总数。所谓锯齿形即相邻元素的大小关系严格交替如 a b c d 或 a b c d。---核心思路用 动态规划 记录最后一步的方向和最后一个元素的值· up[x]以值 x 结尾且最后一步为 上升 的方案数。· down[x]以值 x 结尾且最后一步为 下降 的方案数。转移添加一个新值 x· 要形成 上升到 x前一步必须是下降且结尾值 xnewUp[x] sum(down[0] ... down[x-1])· 要形成 下降到 x前一步必须是上升且结尾值 xnewDown[x] sum(up[x1] ... up[m-1])其中 m r - l 1值域大小为 m。用 前缀和 和 后缀和 加速复杂度 O(n·m)空间 O(m)。---Python3 实现版本一简洁写法直接用前缀/后缀和数组pythonclass Solution:def zigZagArrays(self, n: int, l: int, r: int) - int:MOD 10**9 7m r - l 1# 初始长度为1每个值都可以作为起点up和down都为1up [1] * mdown [1] * mfor _ in range(1, n): # 已经有一个元素再添加 n-1 次# 计算前缀和用于 newUpprefix [0] * (m 1)for i in range(m):prefix[i1] (prefix[i] down[i]) % MOD# 计算后缀和用于 newDownsuffix [0] * (m 1)for i in range(m-1, -1, -1):suffix[i] (suffix[i1] up[i]) % MODnew_up [0] * mnew_down [0] * mfor x in range(m):new_up[x] prefix[x] # sum down[0..x-1]new_down[x] suffix[x1] # sum up[x1..m-1]up, down new_up, new_downreturn (sum(up) sum(down)) % MOD版本二空间更优只用 O(m) 额外数组但这里已经 O(m)上面的代码已经 O(m) 空间时间 O(n·m)。也可以直接利用前缀和计算时滚动但上述写法易读。---例子验证例n3, l1, r3合法数组有[1,3,2], [2,3,1]以及它们的反向起始实际锯齿形要求相邻严格不等且交替三种值。总数为程序结果应该正确。---复杂度· 时间复杂度O(n·m)其中 m r - l 1。· 空间复杂度O(m)。---注意事项· 如果 n 1任何单个元素都是锯齿形无相邻比较返回 m。· 取模 10^97。· 值域可能很大r-l 很大但题目给定限制内可以接受。以上即为 Python3 的完整解法。