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

福大大架构师每日一题

发布于 2025-03-24 06:04:07

5700

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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-*-

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

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

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

    for i inrange(1, n):
        d = max(0, nums[i] - nums[i - 1])
        for j inrange(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)