Skip to content

Latest commit

 

History

History
256 lines (210 loc) · 7.22 KB

README.md

File metadata and controls

256 lines (210 loc) · 7.22 KB
Raw
comments difficulty edit_url rating source tags
true
困难
2323
第 410 场周赛 Q4
数组
数学
动态规划
组合数学
前缀和

3251. 单调数组对的数目 II

English Version

题目描述

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

解释：

单调数组对包括：

  1. ([0, 1, 1], [2, 2, 1])
  2. ([0, 1, 2], [2, 2, 0])
  3. ([0, 2, 2], [2, 1, 0])
  4. ([1, 2, 2], [1, 1, 0])

示例 2：

输入：nums = [5,5,5,5]

输出：126

 

提示：

  • 1 <= n == nums.length <= 2000
  • 1 <= nums[i] <= 1000

解法

方法一：动态规划 + 前缀和优化

我们定义 $f[i][j]$ 表示下标 $[0,..i]$ 的单调数组对的数目，且 $arr1[i] = j$。初始时 $[i][j] = 0$，答案为 $\sum_{j=0}^{\textit{nums}[n-1]} f[n-1][j]$。

当 $i = 0$ 时，有 $[0][j] = 1$，其中 $0 \leq j \leq \textit{nums}[0]$。

当 $i &gt; 0$ 时，我们可以根据 $f[i-1][j']$ 计算 $f[i][j]$。由于 $\textit{arr1}$ 是单调非递减的，因此 $j' \leq j$。又由于 $\textit{arr2}$ 是单调非递增的，因此 $\textit{nums}[i] - j \leq \textit{nums}[i - 1] - j'$。即 $j' \leq \min(j, j + \textit{nums}[i - 1] - \textit{nums}[i])$。

答案为 $\sum_{j=0}^{\textit{nums}[n-1]} f[n-1][j]$。

时间复杂度 $O(n \times m)$，空间复杂度 $O(n \times m)$。其中 $n$ 表示数组 $\textit{nums}$ 的长度，而 $m$ 表示数组 $\textit{nums}$ 中的最大值。

Python3

class Solution:
    def countOfPairs(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        n, m = len(nums), max(nums)
        f = [[0] * (m + 1) for _ in range(n)]
        for j in range(nums[0] + 1):
            f[0][j] = 1
        for i in range(1, n):
            s = list(accumulate(f[i - 1]))
            for j in range(nums[i] + 1):
                k = min(j, j + nums[i - 1] - nums[i])
                if k >= 0:
                    f[i][j] = s[k] % mod
        return sum(f[-1][: nums[-1] + 1]) % mod

Java

class Solution {
    public int countOfPairs(int[] nums) {
        final int mod = (int) 1e9 + 7;
        int n = nums.length;
        int m = Arrays.stream(nums).max().getAsInt();
        int[][] f = new int[n][m + 1];
        for (int j = 0; j <= nums[0]; ++j) {
            f[0][j] = 1;
        }
        int[] g = new int[m + 1];
        for (int i = 1; i < n; ++i) {
            g[0] = f[i - 1][0];
            for (int j = 1; j <= m; ++j) {
                g[j] = (g[j - 1] + f[i - 1][j]) % mod;
            }
            for (int j = 0; j <= nums[i]; ++j) {
                int k = Math.min(j, j + nums[i - 1] - nums[i]);
                if (k >= 0) {
                    f[i][j] = g[k];
                }
            }
        }
        int ans = 0;
        for (int j = 0; j <= nums[n - 1]; ++j) {
            ans = (ans + f[n - 1][j]) % mod;
        }
        return ans;
    }
}

C++

class Solution {
public:
    int countOfPairs(vector<int>& nums) {
        const int mod = 1e9 + 7;
        int n = nums.size();
        int m = *max_element(nums.begin(), nums.end());
        vector<vector<int>> f(n, vector<int>(m + 1));
        for (int j = 0; j <= nums[0]; ++j) {
            f[0][j] = 1;
        }
        vector<int> g(m + 1);
        for (int i = 1; i < n; ++i) {
            g[0] = f[i - 1][0];
            for (int j = 1; j <= m; ++j) {
                g[j] = (g[j - 1] + f[i - 1][j]) % mod;
            }
            for (int j = 0; j <= nums[i]; ++j) {
                int k = min(j, j + nums[i - 1] - nums[i]);
                if (k >= 0) {
                    f[i][j] = g[k];
                }
            }
        }
        int ans = 0;
        for (int j = 0; j <= nums[n - 1]; ++j) {
            ans = (ans + f[n - 1][j]) % mod;
        }
        return ans;
    }
};

Go

func countOfPairs(nums []int) (ans int) {
	const mod int = 1e9 + 7
	n := len(nums)
	m := slices.Max(nums)
	f := make([][]int, n)
	for i := range f {
		f[i] = make([]int, m+1)
	}
	for j := 0; j <= nums[0]; j++ {
		f[0][j] = 1
	}
	g := make([]int, m+1)
	for i := 1; i < n; i++ {
		g[0] = f[i-1][0]
		for j := 1; j <= m; j++ {
			g[j] = (g[j-1] + f[i-1][j]) % mod
		}
		for j := 0; j <= nums[i]; j++ {
			k := min(j, j+nums[i-1]-nums[i])
			if k >= 0 {
				f[i][j] = g[k]
			}
		}
	}
	for j := 0; j <= nums[n-1]; j++ {
		ans = (ans + f[n-1][j]) % mod
	}
	return
}

TypeScript

function countOfPairs(nums: number[]): number {
    const mod = 1e9 + 7;
    const n = nums.length;
    const m = Math.max(...nums);
    const f: number[][] = Array.from({ length: n }, () => Array(m + 1).fill(0));
    for (let j = 0; j <= nums[0]; j++) {
        f[0][j] = 1;
    }
    const g: number[] = Array(m + 1).fill(0);
    for (let i = 1; i < n; i++) {
        g[0] = f[i - 1][0];
        for (let j = 1; j <= m; j++) {
            g[j] = (g[j - 1] + f[i - 1][j]) % mod;
        }
        for (let j = 0; j <= nums[i]; j++) {
            const k = Math.min(j, j + nums[i - 1] - nums[i]);
            if (k >= 0) {
                f[i][j] = g[k];
            }
        }
    }
    let ans = 0;
    for (let j = 0; j <= nums[n - 1]; j++) {
        ans = (ans + f[n - 1][j]) % mod;
    }
    return ans;
}