当前位置：首页 > article >正文

【多维DP】【准NOI难度】力扣3251. 单调数组对的数目 II

article 2024/12/23 18:33:32

给你一个长度为 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

动态规划

class Solution {
public:
    int countOfPairs(vector<int>& nums) {
        const int MOD = 1'000'000'007;
        int n = nums.size();
        int m = ranges::max(nums);
        vector f(n, vector<long long>(m + 1));
        vector<long long> s(m + 1);

        fill(f[0].begin(), f[0].begin() + nums[0] + 1, 1);
        for (int i = 1; i < n; i++) {
            partial_sum(f[i - 1].begin(), f[i - 1].end(), s.begin()); // f[i-1] 的前缀和
            for (int j = 0; j <= nums[i]; j++) {
                int max_k = j + min(nums[i - 1] - nums[i], 0);
                f[i][j] = max_k >= 0 ? s[max_k] % MOD : 0;
            }
        }

        return reduce(f[n - 1].begin(), f[n - 1].end(), 0LL) % MOD;
    }
};

时间复杂度：O(nm)，其中 n 是 nums 的长度，m=max(nums)。
空间复杂度：O(nm)。

这道题由于他要求arr1和arr2对应的arr1[i] + arr2[i] = nums[i]，那么也就是说我们直到arr1的话，就可以知道arr2是多少。但是由于arr1是非递减的，而arr2是非递增的，所以arr2的范围不是单纯的nums[i]-arr1[i]。首先由于arr1是非递减的，那么也就是说arr1[i] >= arr1[i-1]，然后arr2是非递增的，也就是说arr2[i] <= arr2[i-1]。我们假设arr1[i]为j，arr1[i-1]为k，arr2[i] = nums[i] - j而arr2[i-1] = nums[i-1] - k。那么我们可以列出算式nums[i-1] - k >= nums[i] - j。经过变换后得到k <= nums[i-1] - nums[i] + j。也就是说k的最大值就是nums[i-1] + nums[i] + j。而k的最大值在最小的情况下就是等于j，所以我们可以列出min(nums[i-1] - nums[i] + j, j)，化简后就是int max_k = j + min(nums[i - 1] - nums[i], 0);。

我们为什么要求最大k？原因是我们定义了一个二维数组f[i][j]用来表示索引0到索引i并且arr1[i]以j为结尾的单调数组对的数目。我们在递推过程中，我们遍历不同j为结尾，并且以j为结尾的单调组数目可以由f[i-1]的上一个状态并且不同结尾的数进行状态转换而来。那么我们知道了最大值k，我们就可以知道当前f[i][j]可以由f[i-1][0],f[i-1][1]…f[i-1][k]进行状态转移而来。为了避免状态转移过程中都计算f[i-1][0]+…+f[i-1][k]的值，我们可以计算上一个状态的前缀和，当我们知道最大的k的时候就可以直接使用。

由于arr1和arr2都是非负数，所以max_k必须大于0，f[i][j]才可以由上一个状态进行状态转移而来.

最后将f[i-1]的不同j为结尾的情况累加到一起就是答案。

该方法可以进行空间优化，这里不细说

还有一种O(n)的做法，是通过数学排列组合的方式，以后补充

查看全文

http://www.kler.cn/a/448249.html