2025-03-23：单调数组对的数目Ⅱ。用go语言，给定一个长度为 n 的正整数数组 nums，我们需要找出所有的单调数组对。

单调数组对的定义是：两个非负整数数组 (arr1, arr2) 同时满足以下条件：

1.两个数组均为长度 n。

2.arr1 是单调非递减的，即 arr1[0] <= arr1[1] <= … <= arr1[n - 1]。

3.arr2 是单调非递增的，即 arr2[0] >= arr2[1] >= … >= arr2[n - 1]。

4.对于所有的 0 <= i <= n - 1，arr1[i] + arr2[i] 必须等于 nums[i]。

我们需要返回满足条件的单调数组对的总数。由于结果可能很大，因此需要将其对 1000000007 进行取余。

1 <= n == nums.length <= 2000。

1 <= nums[i] <= 1000。

输入：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])

题目来自leetcode3251。

大体步骤如下：

1. 初始化变量：首先统计nums数组中最大的数m，并初始化一个模数mod为10^9 + 7。创建一个二维数组dp用来存储动态规划的结果，其中dp[i][j]表示在索引为i时，arr1的最后一个元素为j时的方案数。

2. 初始化dp数组：根据nums数组的首个元素，初始化dp[0][a]为1，其中a的范围是从0到nums[0]。

3. 动态规划求解：从第二个元素开始，对于每个元素nums[i]，计算出前一个元素和当前元素的差值d，然后根据动态规划关系式更新dp数组中的值。

   • 对于j从d到nums[i]，如果j等于0，则dp[i][j]等于dp[i-1][j-d]，否则，dp[i][j]等于(dp[i][j-1] + dp[i-1][j-d]) % mod。

4. 统计结果：遍历dp数组的最后一行，将所有元素相加并取模，得到最终的结果res。

总的时间复杂度是O(n * m)，其中n为nums的长度，m为数组中的最大值；额外空间复杂度是O(n * m)，用于存储dp数组。

Go完整代码如下：

package main

import (
	"fmt"
)

func countOfPairs(nums []int) int {
	n := len(nums)
	m := 0
	for _, num := range nums {
		if num > m {
			m = num
		}
	}
	mod := int(1e9 + 7)
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, m+1)
	}
	for a := 0; a <= nums[0]; a++ {
		dp[0][a] = 1
	}
	for i := 1; i < n; i++ {
		d := max(0, nums[i]-nums[i-1])
		for j := d; j <= nums[i]; j++ {
			if j == 0 {
				dp[i][j] = dp[i-1][j-d]
			} else {
				dp[i][j] = (dp[i][j-1] + dp[i-1][j-d]) % mod
			}
		}
	}
	res := 0
	for _, num := range dp[n-1] {
		res = (res + num) % mod
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	nums := []int{2, 3, 2}
	result := countOfPairs(nums)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def count_of_pairs(nums):
    n = len(nums)
    m = max(nums)
    mod = 10**9 + 7

    dp = [[0] * (m + 1) for _ in range(n)]

    for a in range(nums[0] + 1):
        dp[0][a] = 1

    for i in range(1, n):
        d = max(0, nums[i] - nums[i - 1])
        for j in range(d, nums[i] + 1):
            if j == 0:
                dp[i][j] = dp[i - 1][j - d]
            else:
                dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d]) % mod

    res = sum(dp[n - 1]) % mod
    return res

if __name__ == "__main__":
    nums = [2, 3, 2]
    result = count_of_pairs(nums)
    print(result)