目标
给你一个长度为 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 <= 2000
- 1 <= nums[i] <= 1000
思路
有一个长度为 n 正整数数组 nums，可以将其拆成两个数组 arr1 arr2，使之满足 arr1[i] + arr2[i] == nums[i]。问 有多少种拆分方法使得 arr1 非递减 且 arr2 非递增。
与昨天的 3250.单调数组对的数目I 相比，nums[i] 的最大值从 50 变成了 1000。时间复杂度大概为 O(n*m^2)，m 为 nums[i] 的最大值，如果还沿用昨天的解法就会超时。
先将昨天的题目改写为动态规划，定义 dp[i][j] 表示最后一个元素为 j，长度为 i + 1 的满足条件的 arr1 个数。由于 arr1 是非递减的，如果最后一个元素为 arr1[i] = j 那么倒数第二个元素arr1[i - 1] <= j。同时我们还要考虑到 arr2 非递增，即 arr2[i - 1] >= arr2[i]，nums[i - 1] - arr1[i - 1] >= nums[i] - arr1[i]，arr1[i - 1] <= nums[i - 1] - nums[i] + arr1[i]。综上，arr1[i - 1] <= Math.min(j, nums[i - 1] - nums[i] + j)。
经过上面的分析，dp[i][j] = Σdp[i - 1][k]，其中 k ∈ [0, Math.min(j, nums[i - 1] - nums[i] + j)]。这样写会超时，针对每个 j，我们会进行多次重复的计算。
令 d = nums[i - 1] - nums[i]，当 d >= 0 时，上界为 j，否则上界为 j + d。
考虑 nums[i - 1] < nums[i]，即 d < 0：
- 当
arr1[i - 1] = j 时，令arr2[i - 1] = nums[i - 1] - j = a
- 当
arr1[i] = j 时，arr2[i] = nums[i] - arr1[i] = nums[i - 1] - d - j = a - d，d < 0。
也就是说，当 arr1[i] 的取值与上一层一样时，arr2[i] 比上一层的值大了 |d|。为了使第 i 层 arr2 非递增，那么 arr1 的取值只能从 |d| 开始。
它们之间的约束关系是这样的，当 nums[i] 变大，arr1 第 i 层取 j 时，arr2 的第 i 层比上一层增大了 |d|，这时我们必须舍弃 [0, |d|) 的取值，因为它必定大于上一层 arr2 的最大值。然后考虑第 i 层的 arr1 取 [|d|, nums[i]] 的情况，由于第 i 层的 arr2 相比第 i - 1 层增大了 |d|，因此需要减小第 i - 1 层的 arr1，使第 i - 1 层的 arr2 增大。所以第 i 层的 j 对应第 i - 1 层的 j - |d|。
dp[i][j] 的取值类似前缀和，只不过有约束条件，并不是所有值都合法。考虑简单的情况 nums[0] == nums[1] && i == 1，
- 当 j == 0 时，
dp[1][0] = dp[0][0] = 1
- 当 j == 1 时，上一层（i == 0） arr1 可以取 0、1，
dp[1][1] = dp[1][0] + dp[0][1] = 2
- 当 j == 2 时，上一层（i == 0） arr1 可以取 0、1、2，
dp[1][2] = dp[1][1] + dp[0][2] = 3
因此我们有 dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d])。
代码
/**
* @date 2024-11-29 9:39
*/
public class CountOfPairs3251 {
public static int MOD = 1000000007;
public int countOfPairs(int[] nums) {
int res = 0;
int n = nums.length;
int[][] dp = new int[n][1001];
for (int i = 0; i <= nums[0]; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < n; i++) {
int d = Math.max(nums[i] - nums[i - 1], 0);
for (int j = d; j <= nums[i]; j++) {
if (j == 0) {
dp[i][j] = dp[i - 1][0] % MOD;
} else {
dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d]) % MOD;
}
}
}
for (int i : dp[n - 1]) {
res = (res + i) % MOD;
}
return res;
}
}
性能
