以下是 LeetCode 3251. 单调数组对的数目 II 的 TypeScript 实现。

核心思路

与 3250 完全相同，只是 `nums[i]` 的范围扩大到 `1000`，因此 DP 数组维度相应增大。仍采用 动态规划 + 前缀和优化：

- `dp[j]` 表示当前位置 `arr1[i] = j` 的方案数
- 转移时 `prev_j <= min(j, j + nums[i-1] - nums[i])`
- 前缀和数组将区间求和优化到 O(1)

TypeScript 代码

```typescript
function countOfPairs(nums: number[]): number {
    const MOD = 1_000_000_007;
    const n = nums.length;
    const m = Math.max(...nums);
    
    // dp[j] 表示当前位置，arr1[i] = j 的方案数
    let dp: number[] = new Array(m + 1).fill(0);
    
    // 初始化：i = 0 时，arr1[0] 可以是 0 到 nums[0]
    for (let j = 0; j <= nums[0]; j++) {
        dp[j] = 1;
    }
    
    for (let i = 1; i < n; i++) {
        // 计算前缀和：prefix[j] = sum(dp[0..j])
        const prefix: number[] = new Array(m + 1).fill(0);
        prefix[0] = dp[0];
        for (let j = 1; j <= m; j++) {
            prefix[j] = (prefix[j - 1] + dp[j]) % MOD;
        }
        
        const newDp: number[] = new Array(m + 1).fill(0);
        const diff = nums[i - 1] - nums[i];
        
        for (let j = 0; j <= nums[i]; j++) {
            // prev_j <= min(j, j + diff)
            const limit = Math.min(j, j + diff);
            if (limit >= 0) {
                newDp[j] = prefix[limit];
            }
            // limit < 0 时，newDp[j] 保持为 0
        }
        
        dp = newDp;
    }
    
    // 答案为所有 dp[j] 之和（j 从 0 到 nums[n-1]）
    let ans = 0;
    for (let j = 0; j <= nums[n - 1]; j++) {
        ans = (ans + dp[j]) % MOD;
    }
    
    return ans;
}
```

复杂度分析

维度    复杂度    
时间    O(n × m)，`n <= 2000`，`m = max(nums) <= 1000`    
空间    O(m)，滚动数组优化    

关键点

- 前缀和优化：`prefix[j] = (prefix[j-1] + dp[j]) % MOD`，将 `sum(dp[0..k])` 的计算降到 O(1)
- 负数处理：`limit = Math.min(j, j + diff)` 可能为负，此时无合法前驱，保持 0
- 滚动数组：每轮只保留上一行状态，空间复杂度 O(m)
- 取模：每次加法后取模，防止整数溢出（TypeScript 中 `number` 为双精度浮点，最大安全整数约 9×10¹⁵，本题中间结果在可控范围内，但仍建议取模）