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)个逆序对的方案数。
  即动态规划状态转移方程为
  $$dp[i][j]=\sum _{k=1}^{i}dp[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)$，会超时，所以要进行优化。
  观察dp[i][j-1]和dp[i][j]的状态转移方程：
  $$dp[i][j-1]=\sum _{k=0}^{i}dp[i-1][j-1-k]$$
  $$dp[i][j]=\sum _{k=0}^{i}dp[i-1][j-k]$$
  可以得到从dp[i][j-1]到dp[i][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][…]转移而来，因此可以对空间进行优化，使用两个一维数组进行状态转移。

Java实现

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] * kfor i in range(2, n+1):next_dp = [1] + [0] * kfor j in range(1, k+1):next_dp[j] = (next_dp[j-1] + dp[j] - (dp[j-i] if j >= i else 0)) % MODdp = next_dpreturn dp[-1]