title
给你一个长度为 n 的 正 整数数组 nums 。
如果两个 非负 整数数组 (arr1, arr2) 满足以下条件，我们称它们是 单调 数组对：
- 两个数组的长度都是
n。 arr1是单调 非递减 的，换句话说arr1[0] <= arr1[1] <= ... <= arr1[n - 1]。arr2是单调 非递增 的，换句话说arr2[0] >= arr2[1] >= ... >= arr2[n - 1]。- 对于所有的
0 <= i <= n - 1都有arr1[i] + arr2[i] == nums[i]。
请你返回所有 单调 数组对的数目。
由于答案可能很大，请你将它对 109 + 7 取余 后返回。
示例 1：
输入：nums = [2,3,2]
输出：4
解释：
单调数组对包括：
([0, 1, 1], [2, 2, 1])([0, 1, 2], [2, 2, 0])([0, 2, 2], [2, 1, 0])([1, 2, 2], [1, 1, 0])
示例 2：
输入：nums = [5,5,5,5]
输出：126
提示：
1 <= n == nums.length <= 20001 <= nums[i] <= 1000
solution
基础动态规划 + 前缀和优化
class Pre:
def __init__(self, arr):
pre = [0]
for i in range(len(arr)):
pre.append(pre[-1] + arr[i])
self.pre = pre
# Get the sum of [l,r], from 0
def get_pre(self, l, r):
return self.pre[r + 1] - self.pre[l]
class Solution:
def countOfPairs(self, nums: List[int]) -> int:
MOD = int(1e9 + 7)
ans = 0
N = max(nums)
n = len(nums)
dp = [[0 for _ in range(N + 1)] for _ in range(n)]
for i in range(nums[0] + 1):
dp[0][i] = 1
for i in range(1, n):
y = nums[i]
x = nums[i - 1]
pre = Pre(dp[i - 1])
for j in range(y + 1):
max_k = min(j, x - y + j)
if max_k >= 0:
dp[i][j] = pre.get_pre(0, max_k) % MOD
return sum(dp[-1][:nums[-1] + 1]) % MOD