html网站地图在线生成,廊坊做网站公司,seo关键词挖掘,网站建设优化方案问题背景
给你一个长度为 n n n 的 正 整数数组 n u m s nums nums。 如果两个 非负 整数数组 ( a r r 1 , a r r 2 ) (arr_1, arr_2) (arr1,arr2) 满足以下条件#xff0c;我们称它们是 单调 数组对#xff1a; 两个数组的长度都是 n n n。 a r r 1 arr_1 arr1 是…问题背景
给你一个长度为 n n n 的 正 整数数组 n u m s nums nums。 如果两个 非负 整数数组 ( a r r 1 , a r r 2 ) (arr_1, arr_2) (arr1,arr2) 满足以下条件我们称它们是 单调 数组对 两个数组的长度都是 n n n。 a r r 1 arr_1 arr1 是单调 非递减 的换句话说 a r r 1 [ 0 ] ≤ a r r 1 [ 1 ] ≤ . . . ≤ a r r 1 [ n − 1 ] arr_1[0] \le arr_1[1] \le ... \le arr_1[n - 1] arr1[0]≤arr1[1]≤...≤arr1[n−1]。 a r r 2 arr_2 arr2 是单调 非递增 的换句话说 a r r 2 [ 0 ] ≤ a r r 2 [ 1 ] ≤ . . . ≤ a r r 2 [ n − 1 ] arr_2[0] \le arr_2[1] \le ... \le arr_2[n - 1] arr2[0]≤arr2[1]≤...≤arr2[n−1]。对于所有的 0 ≤ i ≤ n − 1 0 \le i \le n - 1 0≤i≤n−1 都有 a r r 1 [ i ] a r r 2 [ i ] n u m s [ i ] arr_1[i] arr_2[i] nums[i] arr1[i]arr2[i]nums[i]。
请你返回所有 单调 数组对的数目。 由于答案可能很大请你将它对 1 0 9 7 10 ^ 9 7 1097 取余 后返回。
数据约束 1 ≤ n n u m s . l e n g t h ≤ 2000 1 \le n nums.length \le 2000 1≤nnums.length≤2000 1 ≤ n u m s [ i ] ≤ 50 1 \le nums[i] \le 50 1≤nums[i]≤50
解题过程
周赛三四题的水准两道题目只在数据规模上有差异目前只能尝试写灵神题解的解释。 这题虽然对两个数组有要求但是实际上只需要枚举其中一个数组的情况把对另外一个数组中元素的要求当成约束就行。 根据动态规划缩小问题规模的思想
原问题是下标 0 0 0 到 n − 1 n - 1 n−1中的单调数组对的个数且 a r r 1 [ n − 1 ] j 0 , 1 , 2 , . . . , n u m s [ n − 1 ] arr_1[n−1] j 0, 1, 2, ..., nums[n - 1] arr1[n−1]j0,1,2,...,nums[n−1]。子问题是下标 0 0 0 到 i i i 中的单调数组对的个数且 a r r 1 [ i ] j arr_1[i] j arr1[i]j将其记作 d p [ i ] [ j ] dp[i][j] dp[i][j]。
用 k k k表示 a r r 1 [ i − 1 ] arr_1[i−1] arr1[i−1]那么根据约束条件 { a r r 1 [ i − 1 ] ≤ a r r 1 [ i ] a r r 2 [ i − 1 ] ≥ a r r 2 [ i ] \ \begin{cases} arr_1[i - 1] \le arr_1[i] \\ arr_2[i - 1] \ge arr_2[i] \\ \end{cases} {arr1[i−1]≤arr1[i]arr2[i−1]≥arr2[i]即 { k ≤ j n u m s [ i − 1 ] − k ≥ n u m s [ i ] − j \ \begin{cases} k \le j \\ nums[i - 1] - k \ge nums[i] - j \\ \end{cases} {k≤jnums[i−1]−k≥nums[i]−j可以得到 k k k 的上界。 解得 k ≤ m i n ( j , n u m s [ i − 1 ] − n u m s [ i ] j ) j m i n ( n u m s [ i − 1 ] − n u m s [ i ] , 0 ) k \le min(j, nums[i - 1] - nums[i] j) j min(nums[i - 1] - nums[i], 0) k≤min(j,nums[i−1]−nums[i]j)jmin(nums[i−1]−nums[i],0)由于所有数组中的元素都是非负的而 n u m s [ i ] a r r 1 [ i ] a r r 2 [ i ] nums[i] arr_1[i] arr_2[i] nums[i]arr1[i]arr2[i]所以 k ≤ n u m s [ i − 1 ] k \le nums[i - 1] k≤nums[i−1]。 记 m a x K j m i n ( n u m s [ i − 1 ] − n u m s [ i ] , 0 ) maxK j min(nums[i - 1] - nums[i], 0) maxKjmin(nums[i−1]−nums[i],0)那么 d p [ i ] [ j ] { 0 m a x K 0 Σ k 0 m a x K d p [ i − 1 ] [ k ] m a x K ≥ 0 dp[i][j] \begin{cases} 0 maxK \lt 0 \\ \mathop{\Sigma} \limits _ {k 0} ^ {maxK} dp[i - 1][k] maxK \ge 0 \\ \end{cases} dp[i][j]⎩ ⎨ ⎧0k0ΣmaxKdp[i−1][k]maxK0maxK≥0。 这里 Σ k 0 m a x K d p [ i − 1 ] [ k ] \mathop{\Sigma} \limits _ {k 0} ^ {maxK} dp[i - 1][k] k0ΣmaxKdp[i−1][k] 表示对所有的 k k k 从 0 0 0 到 m a x K maxK maxK 的情况求下标 0 0 0 到 i − 1 i - 1 i−1 中的单调数组对的个数之和要求 a r r 1 k arr_1 k arr1k。这显然满足前缀和的定义记 s [ j ] Σ k 0 j d p [ i − 1 ] [ k ] s[j] \mathop{\Sigma} \limits _ {k 0} ^ {j} dp[i - 1][k] s[j]k0Σjdp[i−1][k]那么上述状态转移方程 ( 3 ) (3) (3) 可以简化为 d p [ i ] [ j ] { 0 m a x K 0 s [ m a x K ] m a x K ≥ 0 dp[i][j] \begin{cases} 0 maxK \lt 0 \\ s[maxK] maxK \ge 0 \\ \end{cases} dp[i][j]{0s[maxK]maxK0maxK≥0。 初始值 d p [ 0 ] [ j ] 1 dp[0][j] 1 dp[0][j]1其中 j 0 , 1 , 2 , . . . , n u m s [ 0 ] j 0, 1, 2, ..., nums[0] j0,1,2,...,nums[0]。这表示的是下标 0 0 0 到 0 0 0 中的单调数组对的个数也就是只考虑数组中第一个元素的情况 a r r 1 [ i ] arr_1[i] arr1[i] 可以是合法范围内任意值。
后续还有进一步优化目前一下子掌握不了先暂时放弃。
具体实现
class Solution {// 根据题意定义模数private static final int MOD 1000000007;public int countOfPairs(int[] nums) {int n nums.length;// m 表示 nums 数组中的最大值所有数组中的元素都不会超过这个范围也就是应枚举的最大值int m Arrays.stream(nums).max().getAsInt();long [][] dp new long[n][m 1];long[] preSum new long[m 1];// 填充初始值只考虑数组中第一个元素的情况Arrays.fill(dp[0], 0, nums[0] 1, 1);for(int i 1; i n; i) {// 计算前缀和这是它的定义preSum[0] dp[i - 1][0];for(int k 1; k m; k) {preSum[k] (preSum[k - 1] dp[i - 1][k]) % MOD;}for(int j 0; j nums[i]; j) {int maxK j Math.min(nums[i - 1] - nums[i], 0);dp[i][j] maxK 0 ? preSum[maxK] % MOD : 0;}}// 答案是考虑完数组中最后一个元素之后对所有可能情形求和return (int) (Arrays.stream(dp[n - 1], 0, nums[n - 1] 1).sum() % MOD);}
}
