Tag Archives: 逆序对

LeetCode K Inverse Pairs Array

LeetCode K Inverse Pairs Array 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 ith and jth 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 109 + 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].

给定一个长度为n的,包含1~n这n个数的数组,问使得逆序对有k个的数组排列有多少种。 使用DP求解。假设dp[n][k]表示长度为n的数组,有k个逆序对的排列数,则: dp[n+1][k]=dp[n][k]+dp[n][k-1]+dp[n][k-2]+…+dp[n][k-n] 要求n+1长有k个逆序对的排列数,可以在
  • 长度为n,且有k个逆序对的基础上,把第n+1个数放到原序列的末尾,则不增加逆序对,+dp[n][k],xxxx*(xxxx表示原长度为n的序列,*表示新加入的数)
  • 长度为n,且有k-1个逆序对的基础上,把第n+1个数插入到原序列倒数第一个空位上,xxx*x,因为插入的*是最大的数,和最后一个x形成一个逆序对,使得新的长度为n+1的序列的逆序对=k-1+1=k,所以+dp[n][k-1]
  • 类似的,xx*xx,+dp[n][k-2]
  • x*xxx,+dp[n][k-3]
  • *xxxx,+dp[n][k-4]
因为远序列长度为n,所以插入的*最多只能增加n个逆序对,即上面的最后一种情况,所以原序列至少需要k-n个逆序对,这样插入*之后,才能达到k-n+n=k个逆序对。即以上递推式的最后一项是dp[n][k-n]。 完整代码如下,注意代码中i其实是n+1,所以m的下界是k-n=j-(i-1)=j-i+1,所以m>j-i。 [cpp] const int kMOD = 1000000007; class Solution { public: int kInversePairs(int n, int k) { vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0)); dp[1][0] = 1; // 长度为1,逆序对为0,只有一种情况 for (int i = 2; i <= n; ++i) { for (int j = 0; j <= k; ++j) { for (int m = j; m >= 0 && m > j – i; –m) { dp[i][j] += dp[i – 1][m]; } dp[i][j] %= kMOD; } } return dp[n][k]; } }; [/cpp] 本代码提交AC,用时1065MS。时空都还可以优化。 参考:https://discuss.leetcode.com/topic/93710/java-dp-thank-you-so-much-gardenaaa-for-your-advice]]>