K个逆序对数组

本文主要是介绍K个逆序对数组，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/k-inverse-pairs-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public class Solution {

    private static final int MOD = 1000000007;

    public int kInversePairs(int n, int k) {
        int[][] dp = new int[n + 1][k + 1];

        for (int i = 1; i <= n; ++i) {
            dp[i][0] = 1;
        }

        /**
         * dp[i][j]: dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-i+1]
         *
         * dp[i][j-1] = dp[i-1][j-1] + ... + dp[i-1][j-i]
         */
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= Math.min(k, i * (i - 1) / 2); j++) {
                int val = (dp[i - 1][j] + MOD - ((j - i) >= 0 ? dp[i - 1][j - i] : 0)) % MOD;
                dp[i][j] = (dp[i][j - 1] + val) % MOD;
            }
        }
        return dp[n][k];
    }
}

这篇关于K个逆序对数组的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！