3250.单调数组对的数目I

链接：3250.单调数组对的数目I
难度：Hard
标签：数组、数学、动态规划、组合数学、前缀和
简介：请你返回所有 单调 数组对的数目。

题解 1 - python

• 编辑时间：2024-11-28
• 执行用时：2817ms
• 内存消耗：123.61MB
• 编程语言：python
• 解法介绍：dfs

class Solution:
    def countOfPairs(self, nums: List[int]) -> int:
        n = len(nums)
        @cache
        def dfs(idx: int, arr1: int, arr2: int) -> int:
            if idx == n: return 1
            res = 0
            for num1 in range(nums[idx] + 1):
                num2 = nums[idx] - num1
                if arr1 <= num1 and arr2 >= num2:
                    res += dfs(idx + 1, num1, num2)
            return res
        return dfs(0, 0, 50) % (10 ** 9 + 7)