K个逆序对数组

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

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

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

问题分析:
dp[n][k]表示1到n的数字中,逆序对的个数为k的不同数组的个数

如果n放在最后的位置,那么k个逆序对就在前面n-1的数组中
如果n放在倒数第二个位置,那么就会出现一个逆序对,则前面n-1的数组中有k-1个逆序对

如果n放在第一个位置,那么就会出现n-1个逆序对,则前面n-1的数组中有k-n+1个逆序对

递推关系:dp[n][k] = dp[n - 1][k] + dp[n - 1][k - 1] + dp[n - 1][k - 2] + … + dp[n - 1][k+1-n+1] + dp[n -1][k - n + 1]
dp[n][k + 1] = dp[n - 1][k + 1] + dp[n - 1][k] + … +dp[n - 1][k + 1 -n + 1]

        因此: dp[n][k + 1] = dp[n - 1][k + 1] + dp[n][k] - dp[n - 1][k - n + 1]
        由于dp[n][k]可能出现负数,因此dp[n][k] = dp[n][k] + MOD

问题求解:

class Solution {
    public int kInversePairs(int n, int k) {
        long[][] dp = new long[n + 1][k + 1];
    if(k > n*(n - 1) / 2 || k < 0)
        return 0;
    if(k == 0 || k == n *(n - 1) / 2)
        return 1;

    int mod = 1000000007;
    dp[2][0] = 1;
    dp[2][1] = 1;
    for(int i = 3 ; i <= n ; i ++){
        dp[i][0] = 1;
        for(int j = 1 ; j <= Math.min(k, n * (n - 1) / 2); j ++){
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            if(j >= i)
                dp[i][j] -= dp[i - 1][j - i];
            dp[i][j] = (dp[i][j] + mod) % mod; //处理dp[i][j]为负数的情况
        }
    }
    return (int)dp[n][k];

    }
}

问题总结:
老规矩先可以看一下官方的解析。
我们可以用动态规划的方法来解决本题。

设 f[i][j]f[i][j] 表示我们使用数字 1, 2, \cdots, i1,2,⋯,i 的排列构成长度为 ii 的数组,并且恰好包含 jj 个逆序对的方案数。在进行状态转移时,我们可以考虑第 ii 个元素选取了 1, 2, \cdots, i1,2,⋯,i 中的哪个数字。

假设我们选取了数字 kk,那么数组的前 i-1i−1 个元素由 1, \cdots, k-11,⋯,k−1 以及 k+1, \cdots, ik+1,⋯,i 的某个排列构成。数组中的逆序对的个数可以看成如下的两部分之和:

数字 kk 与前 i-1i−1 个元素产生的逆序对的个数;

前 i-1i−1 个元素「内部」产生的逆序对个数。

对于第一部分而言,我们可以求出:数字 kk 会贡献 i-ki−k 个逆序对,即 k+1, \cdots, ik+1,⋯,i 与 kk 分别产生一个逆序对。

对于第二部分而言,我们希望它能够有 j - (i-k)j−(i−k) 个逆序对,这样才能一共有 jj 个逆序对。由于我们关心的是前 i-1i−1 个元素「内部」产生的逆序对个数,而逆序对只和元素的「相对大小」有关,因此我们可以:

1, \cdots, k-11,⋯,k−1 这些元素保持不变;

k+1, \cdots, ik+1,⋯,i 这些元素均减少 11,变成 k, \cdots, i-1k,⋯,i−1。

使得前 i-1i−1 个元素中,任意两个元素的相对大小都不发生变化。此时,我们的目标变成了「对于 1, 2, \cdots, i-11,2,⋯,i−1,希望它能够有 j-(i-k)j−(i−k) 个逆序对」,这就是动态规划中的子任务 f[i-1][j-(i-k)]f[i−1][j−(i−k)]。

因此,我们就可以通过枚举 kk 得到状态转移方程:

f[i][j] = \sum_{k=1}^i f[i-1][j-(i-k)] = \sum_{k=0}^{i-1} f[i-1][j-k]
f[i][j]=
k=1

i

f[i−1][j−(i−k)]=
k=0

i−1

f[i−1][j−k]

边界条件为:

f[0][0] = 1f[0][0]=1,即不用任何数字可以构成一个空数组,它包含 00 个逆序对;

f[i][j < 0] = 0f[i][j<0]=0,由于逆序对的数量一定是非负整数,因此所有 j < 0j<0 的状态的值都为 00。我们不需要显式地存储这些状态,只需要在进行状态转移遇到这样的项时,注意特殊判断即可。

最终的答案即为 f[n][k]f[n][k]。

优化

上述动态规划的状态数量为 O(nk)O(nk),而求出每一个 f[i][j]f[i][j] 需要 O(n)O(n) 的时间复杂度,因此总时间复杂度为 O(n^2k)O(n
2
k),会超出时间限制,我们必须要进行优化。

我们考虑 f[i][j-1]f[i][j−1] 和 f[i][j]f[i][j] 的状态转移方程:

\left{ \begin{aligned} & f[i][j-1] && = && \sum_{k=0}^{i-1} f[i-1][j-1-k] \ & f[i][j] && = && \sum_{k=0}^{i-1} f[i-1][j-k] \end{aligned} \right.















f[i][j−1]
f[i][j]

=

k=0

i−1

f[i−1][j−1−k]
k=0

i−1

f[i−1][j−k]

可以得到从 f[i][j-1]f[i][j−1] 到 f[i][j]f[i][j] 的递推式:

f[i][j] = f[i][j-1] - f[i-1][j-i] + f[i-1][j]
f[i][j]=f[i][j−1]−f[i−1][j−i]+f[i−1][j]

这样我们就可以在 O(1)O(1) 的时间计算出每个 f[i][j]f[i][j],总时间复杂度降低为 O(nk)O(nk)。

此外,由于 f[i][j]f[i][j] 只会从第 f[i-1][…]f[i−1][…] 和 f[i][…]f[i][…] 转移而来,因此我们可以对动态规划使用的空间进行优化,即使用两个一维数组交替地进行状态转移,空间复杂度从 O(nk)O(nk) 降低为 O(k)O(k)。

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/k-inverse-pairs-array/solution/kge-ni-xu-dui-shu-zu-by-leetcode-solutio-0hkr/
来源:力扣(LeetCode)

上一篇:P7281 [COCI2020-2021#4] Vepar


下一篇:【13】借助微分关系计算一道不定积分