欢迎您访问365答案网,请分享给你的朋友!
生活常识 学习资料

[LeetCode][H0629]K个逆序对数组(Java)(动态规划)

时间:2023-07-08
题目描述

给出两个整数 n 和 k,找出所有包含从 1 到 n 的数字,且恰好拥有 k 个逆序对的不同的数组的个数。

逆序对的定义如下:对于数组的第i个和第 j个元素,如果满i < j且 a[i] > a[j],则其为一个逆序对;否则不是。

由于答案可能很大,只需要返回 答案 mod 109 + 7 的值。

示例 1:

输入: n = 3, k = 0输出: 1解释: 只有数组 [1,2,3] 包含了从1到3的整数并且正好拥有 0 个逆序对。

示例 2:

输入: n = 3, k = 1输出: 2解释: 数组 [1,3,2] 和 [2,1,3] 都有 1 个逆序对。

说明:

n 的范围是 [1, 1000] 并且 k 的范围是 [0, 1000]。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/k-inverse-pairs-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

在思考中发现一个规律,
假如现在要求 ni个数的 ki 个逆序对 (假设此时ki < ni),那么就是

在ni-1个数的ki个逆序对插入 ni 这个数字,不需要新增逆序对,将其添加到最后一位即可。即dp[ni-1][ki] += dp[ni-1][ki]

在ni-1个数的ki-1个逆序对插入 ni 这个数字,使得新增一个逆序对,只需要把 ni 插入到最后一个和倒数第二个数的中间就好了,这样ni只会和之前的最后一个数字形成逆序对。即dp[ni][ki] += dp[ni-1][ki-1]

在ni-1个数的ki-2个逆序对中,将ni插入到倒数第二个数和倒数第三个数的中间。ni和最后两个数字形成逆序对。即dp[ni][ki] += dp[ni-1][ki-2]


以此类推,可以得到

当 ki < ni 时,
f(ni)(ki) = f(ni-1)(0) + f(ni-1)(1) + f(ni-1)(2) + … + f(ni-1)(ki-1) + f(ni-1)(ki)

同理,由于 f(ni)(ki-1) = f(ni-1)(0) + … + f(ni-1)(ki-1)
得:f(ni)(ki) = f(ni)(ki-1) + f(ni-1)(ki)

但是还有特殊情况,ki 大于 ni 时,将ni插入f(ni-1)(0)、…、f(ni-1)(ki-ni)的第一位都不够满足 ki 的对数要求,那么需要将上述公式减去不能满足的个数
也就是f(ni)(ki) 应该从 f(ni-1)(ki-ni+1) 开始算起

即: f(ni)(ki) = f(ni-1)(ki-ni+1) + … + f(ni-1)(ki-1) + f(ni-1)(ki)
同理,f(ni)(ki-1) = f(ni-1)(ki-ni) + … + f(ni-1)(ki-1)
得:f(ni)(ki)= f(ni)(ki-1) - f(ni-1)(ki-ni) + f(ni-1)(ki)

综合两种情况,得到状态转移方程为:f(ni)(ki)= f(ni)(ki-1) - (ki>=ni?f(ni-1)(ki-ni):0) + f(ni-1)(ki)

反思错误

1、一开始没有考虑到 ki 大于 ni 的情况,导致数量过多
2、一开始使用 mod 求余,但是有出现数值为负数的情况,由于减的数量没有到达求余等级,但是加的数量求过余了,这样就变成负数了。后来使用加减来求余

Java代码

class Solution { private static final int MOD = (int)1e9 + 7; public int kInversePairs(int n, int k) { int[][] cnt = new int[2][k+1]; cnt[0][0] = 1;// >0数字 0逆序对 -》 1组 cnt[1][0] = 1;// 1数字 0逆序对 -》 1组 // ni 几个数字,,ki 几组逆序对 for(int ni=2;ni<=n;++ni) { // 从两个数字开始 int cur = ni&1, pre = cur^1; for(int ki=1;ki<=k;++ki) { // 从有一个逆序对开始 cnt[cur][ki] = cnt[cur][ki-1] + cnt[pre][ki] - (ki>=ni?cnt[pre][ki-ni]:0); if(cnt[cur][ki] >= MOD) { cnt[cur][ki] -= MOD; } else if (cnt[cur][ki]<0) { cnt[cur][ki] += MOD; } } } return cnt[n&1][k]; }}

执行结果

耗时:14ms,内存:35.3MB

Copyright © 2016-2020 www.365daan.com All Rights Reserved. 365答案网 版权所有 备案号:

部分内容来自互联网,版权归原作者所有,如有冒犯请联系我们,我们将在三个工作时内妥善处理。