2025-03-22：单调数组对的数目Ⅰ。用go语言，给定一个长度为n的正整数数组nums，求满足以下条件的非负整数数组(arr1, arr2)构成的单调数组对的数量：

1.arr1为非递减数组，即arr1[0] <= arr1[1] <= … <= arr1[n - 1]。

2.arr2为非递增数组，即arr2[0] >= arr2[1] >= … >= arr2[n - 1]。

3.对于所有的i (0 <= i <= n - 1)，有arr1[i] + arr2[i] = nums[i]。

返回满足条件的单调数组对数量模除1000000007后的结果。

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

1 <= nums[i] <= 50。

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

题目来自leetcode3250。

大体步骤如下：

1. 初始化参数：

   • 初始化一个长度为 n 的正整数数组 nums。
   • 计算数组 nums 的长度 n。
   • 设置初始值 m 为 0（用于找到 nums 中的最大值）。
   • 初始化 mod 为 (10^9 + 7)（取模用）。
   • 创建一个二维动态规划数组 dp，大小为 n x m+1。

2. 填充动态规划数组 dp：

   • 遍历 nums 中的每个元素，找到最大值 m。
   • 使用动态规划数组 dp 存储结果。
   • 对于每个元素 num[i]，从 d = max(0, num[i] - num[i-1]) 开始，遍历 j 从 d 到 num[i]。
   • 确定 dp[i][j] 的值：
     • 若 j 为 0，则 dp[i][j] 等于 dp[i-1][j-d]。
     • 否则，dp[i][j] 等于 (dp[i][j-1] + dp[i-1][j-d]) 模 mod 的结果。

3. 计算满足条件的单调数组对数量：

   • 遍历 dp 的最后一行，累加每个元素的值，相当于将 arr1[i] + arr2[i] 的和加起来。
   • 结果取模操作：res += num) % mod。
   • 返回最终结果 res。

总的时间复杂度：

• 填充动态规划数组 dp 的时间复杂度为 O(n * m)。
• 计算满足条件的单调数组对数量的时间复杂度为 O(n)。

总的额外空间复杂度：

• 动态规划数组 dp 占用的额外空间为 O(n * m)。

综合而言，总的时间复杂度约为 O(n * m)，总的额外空间复杂度为 O(n * m)，其中 n 为数组 nums 的长度，m 为数组 nums 中的最大值。

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[-1]) % mod
    return res

def main():
    nums = [2, 3, 2]
    result = count_of_pairs(nums)
    print(result)

if __name__ == "__main__":
    main()