Hard

题目描述

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

返回单调对的数目。

由于答案可能很大，请返回答案对 10^9 + 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] <= 50

解题思路

这是一个经典的动态规划问题。关键思路是定义状态 dp[i][j] 表示前 i 个位置，且 arr1[i-1] = j 的单调对数量。

状态转移分析：

  1. 对于位置 i，如果 arr1[i] = j，那么 arr2[i] = nums[i] - j
  2. 由于 arr1 单调非递减，arr2 单调非递增，所以：
    • arr1[i] >= arr1[i-1]，即 j >= prev_j
    • arr2[i] <= arr2[i-1]，即 nums[i] - j <= nums[i-1] - prev_j

约束条件转换：

  • j >= prev_j（arr1 非递减）
  • nums[i] - j <= nums[i-1] - prev_j，即 prev_j <= j + nums[i-1] - nums[i]（arr2 非递增）

优化技巧： 可以使用前缀和优化状态转移，将每次查询区间和的时间从 O(sum) 优化到 O(1)。

算法流程：

  1. 初始化：dp[0][j] = 1 对于所有有效的 j
  2. 对于每个位置 i，计算所有可能的 arr1[i] 值 j 的方案数
  3. 使用前缀和快速计算状态转移
  4. 最终答案是所有 dp[n-1][j] 的和

代码实现

class Solution {
public:
    int countOfPairs(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        
        // dp[i][j] = number of ways to fill first i positions with arr1[i-1] = j
        vector<vector<long long>> dp(n, vector<long long>(51, 0));
        
        // Initialize first position
        for (int j = 0; j <= nums[0]; j++) {
            dp[0][j] = 1;
        }
        
        // Fill the dp table
        for (int i = 1; i < n; i++) {
            vector<long long> prefix(51, 0);
            prefix[0] = dp[i-1][0];
            for (int k = 1; k < 51; k++) {
                prefix[k] = (prefix[k-1] + dp[i-1][k]) % MOD;
            }
            
            for (int j = 0; j <= nums[i]; j++) {
                int maxPrevJ = min(50, j + nums[i-1] - nums[i]);
                if (maxPrevJ >= j) {
                    long long sum = prefix[maxPrevJ];
                    if (j > 0) sum = (sum - prefix[j-1] + MOD) % MOD;
                    dp[i][j] = sum;
                }
            }
        }
        
        long long result = 0;
        for (int j = 0; j <= 50; j++) {
            result = (result + dp[n-1][j]) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def countOfPairs(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        
        # dp[i][j] = number of ways to fill first i positions with arr1[i-1] = j
        dp = [[0] * 51 for _ in range(n)]
        
        # Initialize first position
        for j in range(nums[0] + 1):
            dp[0][j] = 1
        
        # Fill the dp table
        for i in range(1, n):
            # Build prefix sum for optimization
            prefix = [0] * 51
            prefix[0] = dp[i-1][0]
            for k in range(1, 51):
                prefix[k] = (prefix[k-1] + dp[i-1][k]) % MOD
            
            for j in range(nums[i] + 1):
                max_prev_j = min(50, j + nums[i-1] - nums[i])
                if max_prev_j >= j:
                    total = prefix[max_prev_j]
                    if j > 0:
                        total = (total - prefix[j-1]) % MOD
                    dp[i][j] = total
        
        return sum(dp[n-1]) % MOD

public class Solution {
    public int CountOfPairs(int[] nums) {
        const int MOD = 1000000007;
        int n = nums.Length;
        
        // dp[i][j] = number of ways to fill first i positions with arr1[i-1] = j
        long[,] dp = new long[n, 51];
        
        // Initialize first position
        for (int j = 0; j <= nums[0]; j++) {
            dp[0, j] = 1;
        }
        
        // Fill the dp table
        for (int i = 1; i < n; i++) {
            long[] prefix = new long[51];
            prefix[0] = dp[i-1, 0];
            for (int k = 1; k < 51; k++) {
                prefix[k] = (prefix[k-1] + dp[i-1, k]) % MOD;
            }
            
            for (int j = 0; j <= nums[i]; j++) {
                int maxPrevJ = Math.Min(50, j + nums[i-1] - nums[i]);
                if (maxPrevJ >= j) {
                    long sum = prefix[maxPrevJ];
                    if (j > 0) sum = (sum - prefix[j-1] + MOD) % MOD;
                    dp[i, j] = sum;
                }
            }
        }
        
        long result = 0;
        for (int j = 0; j <= 50; j++) {
            result = (result + dp[n-1, j]) % MOD;
        }
        
        return (int)result;
    }
}

var countOfPairs = function(nums) {
    const MOD = 1e9 + 7;
    const n = nums.length;
    
    // dp[i][j] = number of ways to fill first i positions with arr1[i-1] = j
    const dp = Array(n).fill().map(() => Array(51).fill(0));
    
    // Initialize first position
    for (let j = 0; j <= nums[0]; j++) {
        dp[0][j] = 1;
    }
    
    // Fill the dp table
    for (let i = 1; i < n; i++) {
        const prefix = Array(51).fill(0);
        prefix[0] = dp[i-1][0];
        for (let k = 1; k < 51; k++) {
            prefix[k] = (prefix[k-1] + dp[i-1][k]) % MOD;
        }
        
        for (let j = 0; j <= nums[i]; j++) {
            const maxPrevJ = Math.min(50, j + nums[i-1] - nums[i]);
            if (maxPrevJ >= j) {
                let sum = prefix[maxPrevJ];
                if (j > 0) sum = (sum - prefix[j-1] + MOD) % MOD;
                dp[i][j] = sum;
            }
        }
    }
    
    let result = 0;
    for (let j = 0; j <= 50; j++) {
        result = (result + dp[n-1][j]) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n × max_val) = O(n × 50) = O(n)，其中 n 是数组长度，max_val = 50 是数组元素的最大值
空间复杂度O(n × max_val) = O(n × 50) = O(n)，用于存储 DP 状态表

相关题目