Java实现 LeetCode 629 K个逆序对数组（动态规划+数学）

629. K个逆序对数组

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

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

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

假如当前的4个数字的排列方式为：xxxx

再往其中添加一个数字5有如下几种添加方式：

xxxx5

多出0个逆序对，因此有：

f1(5,k)=f(4,k)

xxx5x

多出1个逆序对，因此有：

f2(5,k+1)=f(4,k)=> f2(5,k)=f(4,k-1)

xx5xx

多出1个逆序对，因此有：

f3(5,k+2)=f(4,k)=> f3(5,k)=f(4,k-2)

x5xxx

多出1个逆序对，因此有：

f4(5,k+3)=f(4,k)=> f4(5,k)=f(4,k-3)

5xxxx

多出1个逆序对，因此有：

f5(5,k+4)=f(4,k)=> f5(5,k)=f(4,k-4)

=>

f(5,k) = f1 + f2 + f3 + ... + f5

=>

f(5,k) = f(4,k) + f(4,k-1) + f(4,k-2) + f(4,k-3) + f(4,k-5+1)

=>

f(n,k) = f(n-1,k)+f(n-1,k-1) + f(n-1,k-2) + f(n-1,k-3) + ... + f(n-1,k-n+1)

=>

f(n,k+1) = f(n-1,k+1) + f(n-1,k-1) + f(n-1,k-2) + ... + f(n-1,k-n+2)

=>

f(n,k+1) - f(n,k) = f(n-1,k+1) - f(n-1,k-n+1)

=>

f(n,k+1) = f(n,k) + f(n-1,k+1) - f(n-1,k-n+1)

=>

f(n,k) = f(n,k-1) + f(n-1,k) - f(n-1,k-n)

两个递推公式：

f(n,k) = f(n-1,k)+f(n-1,k-1) + f(n-1,k-2) + f(n-1,k-3) + ... + f(n-1,k-n+1)

f(n,k) = f(n,k-1) + f(n-1,k) - f(n-1,k-n)

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];

    }

}

巴特西

Java实现 LeetCode 629 K个逆序对数组（动态规划+数学）

629. K个逆序对数组

最新文章

热门文章