# Leetcode_629. K Inverse Pairs Array
###### tags: `Leetcode` `Hard`
For an integer array nums, an inverse pair is a pair of integers [i, j] where 0 <= i < j < nums.length and nums[i] > nums[j].
Given two integers n and k, return the number of different arrays consist of numbers from 1 to n such that there are exactly k inverse pairs. Since the answer can be huge, return it modulo 109 + 7.
```text=
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 pairs.
```
``` text=
Example 2:
Input: n = 3, k = 1
Output: 2
Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.
```
#### Explain
如果目前為1~3 到新增4，那麼可以變成```1~3的各種可能 再把4插入的任一個位置，但是只有四個位置可以插進去而已-[begin,1st.2st,end]，如圖所示```
```dp[n][k]=dp[n-1][k](插入尾端，k的次數不會變)+dp[n-1][k-1](插入倒數第二個，inverse pairs加一個)+...+dp[n-1][max(0,k-n-1)]```
下圖我覺得蠻直覺性的，搭配內容再看圖蠻好懂得，至於kmax怎麼得出來的有一個解釋如下:
```because that's the max number of reverse pairs you could get from an array of size n, where every pair of number is in reverse order, i.e the whole array is in descending order.```
### Code
``` c=
class Solution {
public:
int kInversePairs(int N, int K) {
int mod=1e9+7;
if(K>((N-1)*N)/2) return 0;
vector<vector<int>> dp(N+1,vector<int>(K+1,0));
dp[1][0]=1;
for(int n=2;n<=N;n++){
int kmax=(n*(n-1))/2;
int sum=0;
for(int k=0;k<=min(kmax,K);k++){
sum=(sum+dp[n-1][k])%mod;
// dp[n][k] and dp[n-1][k-n] are both modulo 1e9+7 and we cannot guarantee the former is larger than the later.
if(k>=n) sum=(sum-dp[n-1][k-n]+mod)%mod;
dp[n][k]=sum;
// cout << " " << dp[n][k] ;
}
// cout << endl;
}
return dp[N][K];
}
};
```
Sign in with Wallet
Connect another wallet