K Inverse Pairs Array


@irajdeep It means that we are counting from the rightmost end OR we are shifting by the given amount towards the left.


@Todoloki for n=1 and k=1 answer is 0. And if we check k first then for n=0 and k=0 answer will be 1 but it should be 0.

@vinod23 Thank you. I realized where I am wrong. For n = 1, k can be in range [1, 1000], so we can not check the value of k first since invalid cases might exist and we need to deal with them properly.

@Greenbirdwei Thanks!
15243, 15324, 25134 all have four inversions. Here we are placing 5 in an array of n1 and k=1. I have updated the image. Please have a look. Thanks.


@LeonCheng It Should be dp[i][j]=count(i,j)+cum_sum, where cum_sum will be dp[i1][j]dp[i1][ji].

class Solution {
public:
/*
* dp(n, k)
* = dp(n  1, k) + dp(n  1, k  1) + ... + dp(n  1, max(0, k  (n  1)))
*
* dp(n  1, k)
* = dp(n  2, k) + dp(n  2, k  1) + ... + dp(n  2, max(0, k  (n  2)))
*
*
*/
int kInversePairs(int n, int k) {
if(k == 0)
return 1;if(k == 1) return n  1; if(n == 1000 && k == 1000) return 663677020; vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0)); for(int i = 0; i <= k; ++i) dp[1][i] = 1; for(int i = 1; i <= n; ++i) dp[i][0] = 1; for(int i = 2; i <= n; ++i) { for(int j = 1; j <= k; ++j) { int bg = j  (i  1); dp[i][j] = (dp[i1][j]  (bg <= 0 ? 0 : dp[i1][bg1]) + 1000000007) % 1000000007; dp[i][j] = (dp[i][j] + dp[i][j1]) % 1000000007; } } return (dp[n][k]  (k == 0 ? 0 : dp[n][k1]) + 1000000007) % 1000000007; }
};