【Leetcode】629. K Inverse Pairs Array

题目地址：

https://leetcode.com/problems/k-inverse-pairs-array/

给定两个整数 n n n和 k k k， n ≥ 1 n\ge 1 n≥1并且 k ≥ 0 k\ge 0 k≥0，问恰好含 k k k个逆序对的 n n n全排列有多少个。

思路是动态规划。设 f [ n ] [ k ] f[n][k] f[n][k]是恰有 k k k个逆序对的全排列个数，那么可以按照 n n n被排在了哪儿来分类，设全排列出的数组是 A A A，如果 A [ n − 1 ] = n A[n-1]=n A[n−1]=n，那么 n n n贡献的逆序对个数是 0 0 0，所以此时个数是 f [ n − 1 ] [ k ] f[n-1][k] f[n−1][k]；如果 A [ n − 2 ] = n A[n-2]=n A[n−2]=n，那么 n n n贡献的逆序对个数是 1 1 1，所以此时个数是 f [ n − 1 ] [ k − 1 ] f[n-1][k-1] f[n−1][k−1]，以此类推。所以有： f [ n ] [ k ] = ∑ s = 0 min ⁡ { n − 1 , k } f [ n − 1 ] [ k − s ] f[n][k]=\sum_{s=0}^{\min\{n-1,k\}}f[n-1][k-s] f[n][k]=s=0∑min{n−1,k}​f[n−1][k−s]初始条件 f [ 0 ] [ 0 ] = 1 , f [ 0 ] [ . > 0 ] = 0 f[0][0]=1,f[0][.>0]=0 f[0][0]=1,f[0][.>0]=0。而如果直接循环枚举 s s s的话，很多区间和都是重复计算的。考虑： f [ n ] [ k + 1 ] = ∑ s = 0 min ⁡ { n − 1 , k + 1 } f [ n − 1 ] [ k + 1 − s ] = ∑ s = − 1 min ⁡ { n − 2 , k } f [ n − 1 ] [ k − s ] = f [ n − 1 ] [ k + 1 ] + ∑ s = 0 min ⁡ { n − 2 , k } f [ n − 1 ] [ k − s ] f[n][k+1]=\sum_{s=0}^{\min\{n-1,k+1\}}f[n-1][k+1-s]\\=\sum_{s=-1}^{\min\{n-2,k\}}f[n-1][k-s]\\=f[n-1][k+1]+\sum_{s=0}^{\min\{n-2,k\}}f[n-1][k-s] f[n][k+1]=s=0∑min{n−1,k+1}​f[n−1][k+1−s]=s=−1∑min{n−2,k}​f[n−1][k−s]=f[n−1][k+1]+s=0∑min{n−2,k}​f[n−1][k−s]也就是计算的时候，我们维护 f [ n − 1 ] f[n-1] f[n−1]这一行的长 n − 1 n-1 n−1的滑动窗口的和即可。代码如下：

public class Solution {
    public int kInversePairs(int n, int k) {
        int MOD = (int) (1E9 + 7);
        int[][] dp = new int[n + 1][k + 1];
        // 0个数的全排列没有逆序对
        dp[0][0] = 1;
        
        for (int i = 1; i <= n; i++) {
        	// 维护长i的窗口和。注意这里用long，防止溢出
            long sum = 0;
            for (int j = 0; j <= k; j++) {
                sum += dp[i - 1][j];
                // 把脱离了窗口的数删掉
                if (j >= i) {
                    sum -= dp[i - 1][j - i];
                }
                dp[i][j] = (int) (sum % MOD);
            }
        }
        
        return (dp[n][k] + MOD) % MOD;
    }
}
           

时空复杂度 O ( n k ) O(nk) O(nk)。