Description
You are given an array of positive integers nums
of length n
.
We call a pair of non-negative integer arrays (arr1, arr2)
monotonic if:
- The lengths of both arrays are
n
. arr1
is monotonically non-decreasing, in other words,arr1[0] <= arr1[1] <= ... <= arr1[n - 1]
.arr2
is monotonically non-increasing, in other words,arr2[0] >= arr2[1] >= ... >= arr2[n - 1]
.arr1[i] + arr2[i] == nums[i]
for all0 <= i <= n - 1
.
Return the count of monotonic pairs.
Since the answer may be very large, return it modulo 109 + 7
.
Example 1:
Input: nums = [2,3,2]
Output: 4
Explanation:
The good pairs are:
([0, 1, 1], [2, 2, 1])
([0, 1, 2], [2, 2, 0])
([0, 2, 2], [2, 1, 0])
([1, 2, 2], [1, 1, 0])
Example 2:
Input: nums = [5,5,5,5]
Output: 126
Constraints:
1 <= n == nums.length <= 2000
1 <= nums[i] <= 1000
Solution
Python3
class Solution:
def countOfPairs(self, nums: List[int]) -> int:
N = len(nums)
M = 10 ** 9 + 7
dp = [[0] * 1001 for _ in range(N)] # dp[index][amount]
# curr >= prev && (nums[i] - curr) <= (nums[i-1] - prev)
# prev <= curr && prev <= curr - nums[i] + nums[i - 1]
# simplify => prev <= min(curr, curr - nums[i] + nums[i - 1])
# so, prev <= min(curr, curr - nums[i] + nums[i - 1])
# and when prev increases by 1, prev + 1 <= min(curr + 1, curr + 1 - nums[i] + nums[i - 1])
# and it can be seen that the difference is only one, hence can use prefix sum to compute that
for j in range(nums[0] + 1):
dp[0][j] = 1
for i in range(1, N):
ways = 0
prev = 0
for curr in range(nums[i] + 1):
if prev <= min(curr, curr - nums[i] + nums[i - 1]):
ways += dp[i - 1][prev]
ways %= M
prev += 1
dp[i][curr] = ways
res = 0
for curr in range(1001):
res += dp[N - 1][curr]
res %= M
return res
C++
class Solution {
public:
int MOD = 1e9 + 7;
int countOfPairs(vector<int>& nums) {
int n = nums.size();
vector<int> arr1(n);
vector<int> arr2(n);
vector<vector<int>> dp(n, vector<int>(1001, 0));
for (int j = 0; j <= nums[0]; j++)
dp[0][j] = 1;
for (int i = 1; i < n; i++){
int ways = 0;
int k = 0;
for (int j = 0; j <= nums[i]; j++){
// problem I
// for (int j = 0; j <= nums[i]; j++){
// int ways = 0;
// for (int k = 0; k <= 50; k++){
// if (k <= j && nums[i - 1] - k >= nums[i] - j)
// ways = (ways + dp[i - 1][k]) % MOD;
// }
// dp[i][j] = ways;
// }
// problem II
if (k <= min(j, j - (nums[i] - nums[i - 1]))){
ways = (ways + dp[i - 1][k]) % MOD;
k++;
}
dp[i][j] = ways;
}
}
int res = 0;
for (int i = 0; i <= 1000; i++)
res = (res + dp[n - 1][i]) % MOD;
return res;
}
};