Dynamic Programming
Description
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 consisting 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
.
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.
Example 2:
Input: n = 3, k = 1
Output: 2
Explanation: The array [1,3,2] and [2,1,3] have exactly 1 inverse pair.
Constraints:
1 <= n <= 1000
0 <= k <= 1000
Solutions
Solution 1
Python3 Java C++ Go TypeScript
class Solution :
def kInversePairs ( self , n : int , k : int ) -> int :
mod = 10 ** 9 + 7
f = [ 1 ] + [ 0 ] * k
s = [ 0 ] * ( k + 2 )
for i in range ( 1 , n + 1 ):
for j in range ( 1 , k + 1 ):
f [ j ] = ( s [ j + 1 ] - s [ max ( 0 , j - ( i - 1 ))]) % mod
for j in range ( 1 , k + 2 ):
s [ j ] = ( s [ j - 1 ] + f [ j - 1 ]) % mod
return f [ k ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public int kInversePairs ( int n , int k ) {
final int mod = ( int ) 1e9 + 7 ;
int [] f = new int [ k + 1 ] ;
int [] s = new int [ k + 2 ] ;
f [ 0 ] = 1 ;
Arrays . fill ( s , 1 );
s [ 0 ] = 0 ;
for ( int i = 1 ; i <= n ; ++ i ) {
for ( int j = 1 ; j <= k ; ++ j ) {
f [ j ] = ( s [ j + 1 ] - s [ Math . max ( 0 , j - ( i - 1 )) ] + mod ) % mod ;
}
for ( int j = 1 ; j <= k + 1 ; ++ j ) {
s [ j ] = ( s [ j - 1 ] + f [ j - 1 ] ) % mod ;
}
}
return f [ k ] ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public :
int kInversePairs ( int n , int k ) {
int f [ k + 1 ];
int s [ k + 2 ];
memset ( f , 0 , sizeof ( f ));
f [ 0 ] = 1 ;
fill ( s , s + k + 2 , 1 );
s [ 0 ] = 0 ;
const int mod = 1e9 + 7 ;
for ( int i = 1 ; i <= n ; ++ i ) {
for ( int j = 1 ; j <= k ; ++ j ) {
f [ j ] = ( s [ j + 1 ] - s [ max ( 0 , j - ( i - 1 ))] + mod ) % mod ;
}
for ( int j = 1 ; j <= k + 1 ; ++ j ) {
s [ j ] = ( s [ j - 1 ] + f [ j - 1 ]) % mod ;
}
}
return f [ k ];
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 func kInversePairs ( n int , k int ) int {
f := make ([] int , k + 1 )
s := make ([] int , k + 2 )
f [ 0 ] = 1
for i , x := range f {
s [ i + 1 ] = s [ i ] + x
}
const mod = 1e9 + 7
for i := 1 ; i <= n ; i ++ {
for j := 1 ; j <= k ; j ++ {
f [ j ] = ( s [ j + 1 ] - s [ max ( 0 , j - ( i - 1 ))] + mod ) % mod
}
for j := 1 ; j <= k + 1 ; j ++ {
s [ j ] = ( s [ j - 1 ] + f [ j - 1 ]) % mod
}
}
return f [ k ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 function kInversePairs ( n : number , k : number ) : number {
const f : number [] = new Array ( k + 1 ). fill ( 0 );
f [ 0 ] = 1 ;
const s : number [] = new Array ( k + 2 ). fill ( 1 );
s [ 0 ] = 0 ;
const mod : number = 1e9 + 7 ;
for ( let i = 1 ; i <= n ; ++ i ) {
for ( let j = 1 ; j <= k ; ++ j ) {
f [ j ] = ( s [ j + 1 ] - s [ Math . max ( 0 , j - ( i - 1 ))] + mod ) % mod ;
}
for ( let j = 1 ; j <= k + 1 ; ++ j ) {
s [ j ] = ( s [ j - 1 ] + f [ j - 1 ]) % mod ;
}
}
return f [ k ];
}
GitHub