HelloKenLee

Leetcode 629. K Inverse Pairs Array 解题报告

Posted on By KenLee

题目信息

题目: 629. K Inverse Pairs Array
难度: Medium
正确率: 23.35%
问题描述:

Given two integers n and k, find how many different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs.

We define an inverse pair as following: For $i_{th}$ and $j_{th}$ element in the array, if i < j and a[i] > a[j] then it’s an inverse pair; Otherwise, it’s not.

Since the answer may very large, the answer should be modulo $10^9 + 7$.

Example 1:

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:

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

Note:

  1. The integer n is in the range [1, 1000] and k is in the range [0, 1000].

问题分析

  该问题的意思是,给出两个数k和n。假设数列[1…n]某一个排列只有k个逆序的数(对于i < j,有a[i] > a[j]),求这种排列的数量是多少。 因为这个数很大,因此还要把这个数对10^9+7取模。

解题思路

  很明显的一道动态规划的题目。假设我们使用dp[n][k]表示长度为n的数组有k个逆序对的数量,我们这样理解dp[n+1][k+i]: 把数字n+1插入到dp[n][k]中,使得其表示的序列新增i个逆序对。比如当i=0的时候,直接把n+1插入到最后就可以了;当i=1的时候,就把n+1插入到倒数第二位。之后我们就可以得到下表:

n\k 0 1 2 3 4 5 6 7
0 1 0 0 0 0 0 0 0  
1 1 0 0 0 0 0 0 0  
2 1 1 0 0 0 0 0 0  
3 1 2 2 1 0 0 0 0  
4 1 3 5 6 5 3 1 0  
                 

  比如dp[3][0]={"1,2,3"}, dp[2][1]={"1,3,2","2,1,3"}。我们求dp[4][1]事实上就是把4插入到dp[3][0]使得逆序对多1,得到{"1,2,4,3"};再把4插入到d[3][1]使得逆序对多0,得到{"1,3,2,4","2,1,3,4"},因此dp[4][1]=dp[3][0]+dp[3][1]

  我们可以初步推出递推方程dp[n][k]=sum(i = 0..k, dp[n-1][i])。 但是我们发现有一些问题,比如dp[3][3]等于1而不是等于2;这是因为我们插入n的时候,最多只能使n-1的序列的逆序对多n-1,比如dp[2][0]={"1,2"},无论怎么插入,我们都没办法使得其逆序对变成3;这也解释了为什么k很大的时候dp[n][k]会为0。

  修改我们的递推方程, 能得到dp[n][k]=sum(i = k-(n-1)..k, dp[n-1][i])。 比如 dp[4][4] = dp[3][1] + dp[3][2] + dp[3][3] + dp[3][4] = 2+2+1+0=5

  然而这样子的时间复杂度为$O(N^2K)$,会得到TLE。一个简单的优化就是使用dp[n][k-1]来计算dp[n][k],详细可以看代码。

  还有一些杂七杂八的优化: 比如 使用静态变量dp存储已经计算的结果,如果已经计算过了直接返回,使用减法代替取余等等。

结果分析

  • 时间复杂度: $ O(NK) $对于多个样例的最大的$N$和$K$。
  • 空间复杂度: $ O(NK) $DP数组的空间大小。
  • 通过时间: 22 ms
  • 击败: 72.90%

源代码

class Solution {
public:
    int kInversePairs(int n, int k) {
        if(n < maxN && k < maxK){
            return k < res[n].size() ? res[n][k] : 0;
        }
        maxN = max(n, maxN);
        maxK = max(k, maxK);
        for(int _n = 1; _n <= n; ++_n){
            if(res.size() <= _n)
                res.push_back(vector<int> (1,1));
            
            int _k = res[_n].size();
            for(; _k <= k; ++_k){
                int num = res[_n][_k - 1];

                if(_k < res[_n - 1].size())
                    num += res[_n - 1][_k];
                if(_k >= _n)
                    num -= res[_n - 1][_k - _n];

                if(num < 0)
                    num += modulo;
                if(num >= modulo)
                    num -= modulo;
                
                if(num == 0)
                    break;
                    
                res[_n].push_back(num);
                
            }

        }
        return k < res[n].size() ? res[n][k] : 0;
    }
private:
    const int modulo = 1000000000 + 7;
    static vector<vector<int>> res;//res[n][k]表示结果
    static int maxN, maxK;
};

vector<vector<int>> Solution::res(1, vector<int>(1, 1));
int Solution::maxN = 0;
int Solution::maxK = 0;