Leetcode3250. 单调数组对的数目 I

本文主要是介绍Leetcode3250. 单调数组对的数目 I，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Every day a Leetcode

题目来源：3250. 单调数组对的数目 I

解法1：记忆化搜索

题目输入一个数组nums。

假设有两个数组A和B，A递增，B递减，且 Ai + Bi = numsi
​

问有多少对(A,B)数组对。

解法：

代码：

#
# @lc app=leetcode.cn id=3250 lang=python3
#
# [3250] 单调数组对的数目 I
## @lc code=start# 记忆化搜索class Solution:def countOfPairs(self, nums: List[int]) -> int:MOD = 10 ** 9 + 7n = len(nums)@cachedef dfs(i, a):if i == n - 1:return 1res = 0b = nums[i] - afor na in range(nums[i + 1] + 1):nb = nums[i + 1] - naif a <= na and b >= nb:res += dfs(i + 1, na)return res % MODres = 0for num in range(nums[0] + 1):res += dfs(0, num)res %= MODreturn res
# @lc code=end

结果：

复杂度分析：

时间复杂度：O(n * m²)，其中 n 是数组 nums 的长度。

空间复杂度：O(n * m)，其中 n 是数组 nums 的长度。

这篇关于Leetcode3250. 单调数组对的数目 I的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---