【Leetcode 每日一题】3250. 单调数组对的数目 I

问题背景

给你一个长度为 $n$ 的 正 整数数组 $nums$。
如果两个 非负 整数数组 $(ar{r}_1,ar{r}_2)$ 满足以下条件，我们称它们是 单调 数组对：
两个数组的长度都是 $n$。

• $ar{r}_1$ 是单调 非递减 的，换句话说 $ar{r}_1[0]\le ar{r}_1[1]\le ...\le ar{r}_1[n-1]$。
• $ar{r}_2$ 是单调 非递增 的，换句话说 $ar{r}_2[0]\le ar{r}_2[1]\le ...\le ar{r}_2[n-1]$。
• 对于所有的 $0\le i\le n-1$ 都有 $ar{r}_1[i]+ar{r}_2[i]==nums[i]$。

请你返回所有 单调 数组对的数目。
由于答案可能很大，请你将它对 $10^9+7$ 取余 后返回。

数据约束

• $1\le n=nums.length\le 2000$
• $1\le nums[i]\le 50$

解题过程

周赛三四题的水准，两道题目只在数据规模上有差异，目前只能尝试写灵神题解的解释。
这题虽然对两个数组有要求，但是实际上只需要枚举其中一个数组的情况，把对另外一个数组中元素的要求当成约束就行。
根据动态规划缩小问题规模的思想：

• 原问题是下标 $0$ 到$n-1$中的单调数组对的个数，且 $ar{r}_1[n-1]=j=0,1,2,...,nums[n-1]$。
• 子问题是下标 $0$ 到 $i$ 中的单调数组对的个数，且 $ar{r}_1[i]=j$，将其记作 $dp[i][j]$。

用$k$表示$ar{r}_1[i-1]$，那么根据约束条件：$\{\begin{array}{l}ar{r}_1[i-1]\le ar{r}_1[i]\\ ar{r}_2[i-1]\ge ar{r}_2[i]\end{array}$，即$\{\begin{array}{l}k\le j\\ nums[i-1]-k\ge nums[i]-j\end{array}$，可以得到 $k$ 的上界。
解得 $k\le min(j,nums[i-1]-nums[i]+j)=j+min(nums[i-1]-nums[i],0)$，由于所有数组中的元素都是非负的，而 $nums[i]=ar{r}_1[i]+ar{r}_2[i]$，所以 $k\le nums[i-1]$。
记 $maxK=j+min(nums[i-1]-nums[i],0)$，那么$dp[i][j]=\{\begin{array}{ll}0，& maxK<0\\ \underset{k=0}{\overset{maxK}{\Sigma }}dp[i-1][k]，& maxK\ge 0\end{array}$。
这里 $\underset{k=0}{\overset{maxK}{\Sigma }}dp[i-1][k]$ 表示对所有的 $k$ 从 $0$ 到 $maxK$ 的情况，求下标 $0$ 到 $i-1$ 中的单调数组对的个数之和，要求 $ar{r}_1=k$。这显然满足前缀和的定义，记 $s[j]=\underset{k=0}{\overset{j}{\Sigma }}dp[i-1][k]$，那么上述状态转移方程 $(3)$ 可以简化为 $dp[i][j]=\{\begin{array}{ll}0，& maxK<0\\ s[maxK]，& maxK\ge 0\end{array}$。
初始值 $dp[0][j]=1$，其中 $j=0,1,2,...,nums[0]$。这表示的是，下标 $0$ 到 $0$ 中的单调数组对的个数，也就是只考虑数组中第一个元素的情况，$ar{r}_1[i]$ 可以是合法范围内任意值。

后续还有进一步优化，目前一下子掌握不了，先暂时放弃。

具体实现

class Solution {// 根据题意定义模数private static final int MOD = 1000000007;public int countOfPairs(int[] nums) {int n = nums.length;// m 表示 nums 数组中的最大值，所有数组中的元素都不会超过这个范围，也就是应枚举的最大值int m = Arrays.stream(nums).max().getAsInt();long [][] dp = new long[n][m + 1];long[] preSum = new long[m + 1];// 填充初始值，只考虑数组中第一个元素的情况Arrays.fill(dp[0], 0, nums[0] + 1, 1);for(int i = 1; i < n; i++) {// 计算前缀和，这是它的定义preSum[0] = dp[i - 1][0];for(int k = 1; k <= m; k++) {preSum[k] = (preSum[k - 1] + dp[i - 1][k]) % MOD;}for(int j = 0; j <= nums[i]; j++) {int maxK = j + Math.min(nums[i - 1] - nums[i], 0);dp[i][j] = maxK >= 0 ? preSum[maxK] % MOD : 0;}}// 答案是考虑完数组中最后一个元素之后，对所有可能情形求和return (int) (Arrays.stream(dp[n - 1], 0, nums[n - 1] + 1).sum() % MOD);}
}