leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0629.cpp (1045B)

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 };