力扣每日一题 单调数组对的数目(dp)
题目
困难 动态规划
给你一个长度为
n
的 正 整数数组nums
。如果两个 非负 整数数组
(arr1, arr2)
满足以下条件,我们称它们是 单调 数组对:
- 两个数组的长度都是
n
。arr1
是单调 非递减 的,换句话说arr1[0] <= arr1[1] <= ... <= arr1[n - 1]
。arr2
是单调 非递增 的,换句话说arr2[0] >= arr2[1] >= ... >= arr2[n - 1]
。- 对于所有的
0 <= i <= n - 1
都有arr1[i] + arr2[i] == nums[i]
。请你返回所有 单调 数组对的数目。
由于答案可能很大,请你将它对
109 + 7
取余 后返回。示例 1:
输入:nums = [2,3,2]
输出:4
解释:
单调数组对包括:
([0, 1, 1], [2, 2, 1])
([0, 1, 2], [2, 2, 0])
([0, 2, 2], [2, 1, 0])
([1, 2, 2], [1, 1, 0])
示例 2:
输入:nums = [5,5,5,5]
输出:126
提示:
1 <= n == nums.length <= 2000
1 <= nums[i] <= 50
思路
题目要求求出符合条件的数组数量,刚开始想着用搜索来做的,想了一下复杂度太高了,就考虑动态规划
根据题目中 arr1[i] + arr2[i] = nums[i],我们可以知道一旦确定了arr1的取值,arr2也会随之确定,其中 arr2[i]= nums[i]-arr1[i],所以我们直接枚举arr1的情况,通过条件筛选对应的arr2即可
开一个二维数组dp,其中dp[i][j]代表arr1数组第i个数取j时符合条件的数组对的数量
要求第i个数取j时符合条件的数组对的数量就要看第i-1个数取符合条件的数时数组对的数量
要求第i-1个数取j时符合条件的数组对的数量就要看第i-2个数取符合条件的数时数组对的数量
..........................................................
这很动态规划,由子问题求解大问题
初始化
当i=0时,arr1[0]可以取值的范围为0-nums[0],所以先给dp数组的dp[0][0]~dp[0][nums[0]]赋值为1,方便后面迭代计算
当i>=1时,设v2为arr1[i]对应的数,v1为arr1[i-1]对应的数
每次先枚举v2,v2的取值范围为0-nums[i],然后由于arr1数组是非递减的,所以v1<=v2,v1的取值范围为0-v2,此时仅仅只是确定了arr1的条件
for(int i=1;i<n;i++){
//枚举当前位置的数
for(int v2=0;v2<=nums[i];v2++){
//枚举前一个数
for(int v1=0;v1<=v2;v1++){
}
}
}
还要考虑arr2,设v2t为arr2[i]对应的数,v1为arr2[i-1]对应的数
由于v1+v1t=nums[i-1],v2+v2t=nums[i]
可得v1t=nums[i]-v1,v2t=nums[i]-v2
由于arr2数组是非递增的,所以有v1t>=v2t
由以上推导我们利用两层循环筛选符合条件的v1和v2
同时利用题目中arr1[i] + arr2[i] = nums[i]的性质得到arr2对应的v1t和v2t判断条件,符合条件的话就将对应的dp[i-1][v1]累加到dp[i][v2]中
下面上代码
class Solution {
public int countOfPairs(int[] nums) {
int n=nums.length;
int mod=1000000007;
int[][] dp=new int[n][55];
//第一个数字可以取0~nums[0],dp数组全部置为1
for(int i=0;i<=nums[0];i++){
dp[0][i]=1;
}
for(int i=1;i<n;i++){
//枚举当前位置的数
for(int v2=0;v2<=nums[i];v2++){
//枚举前一个数
for(int v1=0;v1<=v2;v1++){
//arr2[i-1]
int v1t=nums[i-1]-v1;
//arr2[i]
int v2t=nums[i]-v2;
//arr2[i-1]>=arr2[i]时才符合条件
if(v1t>=v2t){
dp[i][v2]=(dp[i][v2]+dp[i-1][v1])%mod;
}
}
}
}
int ans=0;
//累加取答案
for(int i=0;i<=nums[n-1];i++){
ans=(ans+dp[n-1][i])%mod;
}
return ans;
}
}