↓Skip to main content
  1. Posts/

LeetCode-3251 单调数组对的数目 II

·1 min·
Table of Contents

LeetCode-3251 单调数组对的数目 II #

Solution 1 #

记 $dp[i][j]$ 为根据 $nums[:i+1]$ 构造, $arr1[i]$ 为 $j$ 的单调数组对的数目. 则有状态转移方程: $$ dp[i][j] = \sum_{k\leq j, nums[i - 1] - k\geq nums[i] - j}dp[i - 1][k] $$

用前缀和优化 dp 计算.

代码如下:

MOD = 1_000_000_007
class Solution:
    def countOfPairs(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0 for _ in range(1001)] for _ in range(n)]
        for j in range(nums[0] + 1):
            dp[0][j] = 1

        for i in range(1, n):
            s = list(accumulate(dp[i - 1]))
            for j in range(0, nums[i] + 1):
                k = min(nums[i - 1] - nums[i], 0) + j
                if k < 0:
                    dp[i][j] = 0
                else:
                    dp[i][j] = (dp[i][j] + s[k]) % MOD
            
        return sum(dp[-1]) % MOD

Solution 2 #

$O(n)$ 组合做法. 参考 两种方法：前缀和优化 DP / 组合数学（Python/Java/C++/Go）.