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 10⁹ + 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]]>