629. K个逆序对数组 #

问题描述#

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

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

由于答案可能很大，只需要返回答案 mod 10⁹ + 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]。

解题思路#

易知 \(n\) 个数按照 \(\boxed{n,n-1,\cdots,2,1}\) 的顺序排列时的逆序对最多，有 \((n-1)+(n-2)+\cdots+1=\frac{n\times(n-1)}{2}\) 个。

用 \(R(n)\) 表示 \(n\) 个数的最多逆序对数量，即 \(R(n)=\sum_{i=1}^{n-1}i=\frac{n\times n-1}{2}\)。

当从 \(n-1\) 个数变为 \(n\) 个数时，最多可以增加 \(n-1\) 个逆序对，因为 \(n-1\) 个数都比 \(n\) 小。

所以只要移动 \(n\) 在 \(n-1\) 个数中的位置，就可以最多增加 \(n-1\) 个逆序对。

用 \(P(n,k)=\{a_1^k,a_2^k,\cdots,a_n^k\}\) 表示 \(n\) 个数时逆序对为 \(k\) 的一个排列，\(k\le R(n)\)。

用 \(dp[n][k]\) 表示 \(n\) 个数中逆序对为 \(k\) 的排列数量。

\(P(n-1,k)=\{a_1^k,a_2^k,\cdots,a_{n-1}^k\}\)，可以通过移动数字 \(n\) 在 \(P(n-1,k)\) 中的位置，来获得 \(n\) 的各个逆序对的数量。

\[ \begin{aligned} &\{a_1^k,a_2^k,\cdots,a_{n-1}^k,\boxed{n}\}\to dp[n-1][k]+0\\ &\{a_1^k,a_2^k,\cdots,\boxed{n},a_{n-1}^k\}\to dp[n-1][k]+1\\ &\vdots\\ &\{\boxed{n},a_1^k,a_2^k,\cdots,a_{n-1}^k\}\to dp[n-1][k]+n-1\\ \end{aligned} \]

所以

\[ \text{dp}[i][j]=\sum_{p=l}^{r} dp[i-1][p] \]

\(l=\max(0,j-(i-1)),r=\min(j,k,R(i-1))\)。

\(n=1,2,3\) 时各个逆序对的数量如下：

\[ \begin{array}{c|c} n\backslash k&0&1&2&3\\\hline 1&1\\ 2&1&1\\ 3&1&2&2&1 \end{array} \]

\[ \begin{aligned} &dp[1][0]=1\\ &dp[2][0]=dp[1][0],dp[2][1]=dp[1][0]\\ &dp[3][0]=dp[2][0],dp[3][1]=dp[2][0]+dp[2][1],dp[3][2]=dp[2][0]+dp[2][1],dp[3][3]=dp[2][1] \end{aligned} \]

class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        MOD = 10 ** 9 + 7
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        dp[1][0] = 1

        prev = 0
        for i in range(2, n + 1):
            cur = prev + i - 1  # i 最多的逆序对数量
            for j in range(1 + min(k, prev)):
                dp[i - 1][j] += j and dp[i - 1][j - 1]
            for j in range(1 + min(k, cur)):
                l, r = max(0, j - i + 1), min(j, k, prev)
                dp[i][j] = (dp[i - 1][r] - (l and dp[i - 1][l - 1])) % MOD
            prev = cur
        return dp[n][k]

629. K个逆序对数组#

问题描述#

解题思路#

629. K个逆序对数组 #