leetcode-k-inverse-pairs-array

发表于   |   分类于 ，   |  

题目大意

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

　　给你n和k，n代表了1,2,3….n的数组，找出数组排列的个数满足，有且只有k个逆序对

Example 1:

1
2
3
4
Input: n = 3, k = 0
Output: 1
Explanation: 
Only the array [1,2,3] which consists of numbers from 1 to 3 has exactly 0 inverse pair.

Example 2:

1
2
3
4
Input: n = 3, k = 1
Output: 2
Explanation: 
The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.

题目分析

　　计数类型的动态规划，推导思路参考了这里:https://discuss.leetcode.com/topic/93815/java-dp-o-nk-solution

考虑dp[n][k]和dp[n-1][j]的关系，分情况，把最大的元素n分别放在数组的第n个位置，第n-1个位置…..第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]

然后k->k+1

dp[n][k+1] = dp[n-1][k+1]+dp[n-1][k]+dp[n-1][k-1]+dp[n-1][k-2]+...+dp[n-1][k+1-n]

两式子相减即可得到递推方程，写code时注意一下边界条件，比如第二维如果小于0，则认为该值为0

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
    // dp[n][k+1] = dp[n][k]+dp[n-1][k+1]-dp[n-1][k+1-n]
    public int kInversePairs(int n, int k) {
        if (k > n * (n - 1) / 2) {
            return 0;
        }
        if (k == 0 || k == n * (n - 1) / 2) {
            return 1;
        }
        int MOD = 1000000007;
        long[][] dp = new long[n + 1][k + 1];
        dp[2][0] = 1;
        dp[2][1] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= k; j++) {
                if (j == i * (i - 1) / 2) {
                    dp[i][j] = 1;
                } else if (j > i * (i - 1) / 2) {
                    dp[i][j] = 0;
                } else {
                    if (j < i) {
                        dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % MOD;
                    } else {
                        dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - i] + MOD) % MOD;
                    }
                }
            }
        }
        return (int)dp[n][k];
    }
}

　　时间复杂度：O(n*k)