leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0629.cpp (1045B)

      1 class Solution {
      2     static const int MOD = 1E9 + 7;
      3 
      4   public:
      5     int kInversePairs(int n, int k) {
      6         static int dp[1001][1001];
      7         memset(dp, 0x00, sizeof(dp));
      8 
      9         dp[0][0] = 1;
     10         for (int i = 1; i <= n; i++) {
     11             for (int j = 0; j <= k; j++) {
     12                 dp[i][j] = (dp[i - 1][j] + (j > 0 ? dp[i][j - 1] : 0)) % MOD;
     13                 if (j >= i) dp[i][j] = (MOD + dp[i][j] - dp[i - 1][j - i]) % MOD;
     14             }
     15         }
     16         return dp[n][k];
     17     }
     18 };
     19 
     20 // Space optimized
     21 class Solution {
     22     static const int MOD = 1E9 + 7;
     23 
     24   public:
     25     int kInversePairs(int n, int k) {
     26         static int dp[2][1001];
     27         memset(dp, 0x00, sizeof(dp));
     28 
     29         dp[0][0] = 1;
     30         for (int i = 1; i <= n; i++) {
     31             for (int j = 0; j <= k; j++) {
     32                 dp[i % 2][j] = (dp[(i - 1) % 2][j] + (j > 0 ? dp[i % 2][j - 1] : 0)) % MOD;
     33                 if (j >= i) dp[i % 2][j] = (MOD + dp[i % 2][j] - dp[(i - 1) % 2][j - i]) % MOD;
     34             }
     35         }
     36         return dp[n % 2][k];
     37     }
     38 };