leetcode

0 class Solution {

1 static const int MOD = 1E9 + 7;

2

3 public:

4 int kInversePairs(int n, int k) {

5 static int dp[1001][1001];

6 memset(dp, 0x00, sizeof(dp));

7

8 dp[0][0] = 1;

9 for (int i = 1; i <= n; i++) {

10 for (int j = 0; j <= k; j++) {

11 dp[i][j] = (dp[i - 1][j] + (j > 0 ? dp[i][j - 1] : 0)) % MOD;

12 if (j >= i) dp[i][j] = (MOD + dp[i][j] - dp[i - 1][j - i]) % MOD;

13 }

14 }

15 return dp[n][k];

16 }

17 };

18

19 // Space optimized

20 class Solution {

21 static const int MOD = 1E9 + 7;

22

23 public:

24 int kInversePairs(int n, int k) {

25 static int dp[2][1001];

26 memset(dp, 0x00, sizeof(dp));

27

28 dp[0][0] = 1;

29 for (int i = 1; i <= n; i++) {

30 for (int j = 0; j <= k; j++) {

31 dp[i % 2][j] = (dp[(i - 1) % 2][j] + (j > 0 ? dp[i % 2][j - 1] : 0)) % MOD;

32 if (j >= i) dp[i % 2][j] = (MOD + dp[i % 2][j] - dp[(i - 1) % 2][j - i]) % MOD;

33 }

34 }

35 return dp[n % 2][k];

36 }

37 };