- 629.K个逆序对数组
- 题目描述
- 思路：动态规划
- Java实现
- Python实现
629.K个逆序对数组 题目描述
K个逆序对数组
思路：动态规划
假定dp[i][j]表示使用数字1、2、…、i的排列构成长度为i的数组，并且恰好包含j个逆序对的方案数。在进行状态转移时，可以考虑第i个元素选取了1、2、…、i中的哪个数字。
假设选定数字k，则数组的前i-1个元素由1、2、…、k-1以及k+1、…、i的某个排列组成，k为最后一个元素，则逆序对的个数可以看做下两个部分的和：
- 数字k与前i-1个元素产生的逆序对的个数；
- 前i-1个元素内部产生的逆序对个数。
对于前一个部分而言，可以求出：数字k会贡献i-k个逆序对，即k+1、…、i与k分别产生一个逆序对。
对于后一个部分而言，希望它能够有j-(i-k)个逆序对，这样才能使数组共有j个逆序对。因为逆序对只与元素的相对大小有关，可以进行如下操作： - 1、…、k-1这些元素保持不变；
- k+1、…、i这些元素均减少1，变成k、…、i-1。
使得前i-1个元素中，任意两个元素的相对大小都不发生变化。此时的目标就变成了对于1、…、i-1的i-1个元素求它有j-(i-k)个逆序对的方案数。
即动态规划状态转移方程为
d p [ i ] [ j ] = ∑ k = 1 i d p [ i − 1 ] [ j − ( i − k ) ] dp[i][j] = sum_{k=1}^{i} dp[i-1][j-(i-k)] dp[i][j]=k=1∑idp[i−1][j−(i−k)]
边界条件为： - dp[0][0] = 1，即长度为0的数组共可以构成有0个逆序对的数组方案数为1。
- dp[i][j<0] = 0，由于逆序对的数量一定是非负整数，因此所有j<0的状态的值都为0。不需要显示存储这些状态，只需要在进行状态转移遇到这样的情况时，处理即可。
最终的答案返回dp[n][k]即可。
因为动态规划的状态数量为O(nk)，而求出每个dp[i][j]需要O(n)的时间复杂度，则总时间复杂度为 O ( n 2 k ) O(n^2k) O(n2k)，会超时，所以要进行优化。
观察dp[i][j-1]和dp[i][j]的状态转移方程：
d p [ i ] [ j − 1 ] = ∑ k = 0 i d p [ i − 1 ] [ j − 1 − k ] dp[i][j-1] = sum_{k=0}^{i}dp[i-1][j-1-k] dp[i][j−1]=k=0∑idp[i−1][j−1−k]
d p [ i ] [ j ] = ∑ k = 0 i d p [ i − 1 ] [ j − k ] dp[i][j] = sum_{k=0}^{i}dp[i-1][j-k] dp[i][j]=k=0∑idp[i−1][j−k]
可以得到从dp[i][j-1]到dp[i][j]的递推式：
d p [ i ] [ j ] = d p [ i ] [ j − 1 ] − d p [ i − 1 ] [ j − i ] + d p [ i − 1 ] [ j ] dp[i][j] = dp[i][j-1] - dp[i-1][j-i] + dp[i-1][j] dp[i][j]=dp[i][j−1]−dp[i−1][j−i]+dp[i−1][j]
另外，由于dp[i][j]只会从第dp[i-1][…]和dp[i][…]转移而来，因此可以对空间进行优化，使用两个一维数组进行状态转移。
class Solution {
private static final int MOD = (int) 1e9+7;
public int kInversePairs(int n, int k) {
int[] dp = new int[k + 1];
Arrays.fill(dp, 0);
dp[0] = 1;
for(int i=2;i<=n;i++){
int[] next_dp = new int[k + 1];
Arrays.fill(next_dp, 0);
next_dp[0] = 1;
for(int j=1;j<=k;j++){
next_dp[j] = (next_dp[j-1] + dp[j]) % MOD;
if(j >= i){
next_dp[j] = (next_dp[j] - dp[j-i] + MOD) % MOD;
}
}
dp = next_dp;
}
return dp[k];
}
}
Python实现
MOD = int(1e9) + 7
class Solution:
def kInversePairs(self, n: int, k: int) -> int:
dp = [1] + [0] * k
for i in range(2, n+1):
next_dp = [1] + [0] * k
for j in range(1, k+1):
next_dp[j] = (next_dp[j-1] + dp[j] - (dp[j-i] if j >= i else 0)) % MOD
dp = next_dp
return dp[-1]
