leetcode

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

1420.cpp (1744B)

      1 
      2 // Top-down
      3 class Solution {
      4     static const int MOD = 1e9 + 7;
      5     static int dp[51][101][51];
      6 
      7   public:
      8     Solution() { memset(dp, 0xFF, sizeof(dp)); }
      9     int numOfArrays(const int n, const int m, int k, int c = 0, int maxi = 0) {
     10         if (c == n) return k == 0;
     11         if (k < 0) return 0;
     12         if (dp[c][maxi][k] != -1) return dp[c][maxi][k];
     13 
     14         int res = 0;
     15         for (int i = 1; i <= maxi; i++) {
     16             res = (res + numOfArrays(n, m, k, c + 1, maxi)) % MOD;
     17         }
     18 
     19         for (int i = maxi + 1; i <= m; i++) {
     20             res = (res + numOfArrays(n, m, k - 1, c + 1, i)) % MOD;
     21         }
     22 
     23         return dp[c][maxi][k] = res;
     24     }
     25 };
     26 
     27 int Solution::dp[51][101][51];
     28 
     29 // Bottom-up
     30 class Solution {
     31     static const int MOD = 1e9 + 7;
     32 
     33   public:
     34     int numOfArrays(const int n, const int m, int k) {
     35         vector<vector<int>> dp(vector(m + 1, vector(k + 1, 0)));
     36         vector<vector<int>> pdp(vector(m + 1, vector(k + 1, 0)));
     37         for (int num = 0; num <= m; num++)
     38             pdp[num][0] = 1;
     39 
     40         for (int i = n - 1; i >= 0; i--) {
     41             for (int maxi = m; maxi >= 0; maxi--) {
     42                 for (int remain = 0; remain <= k; remain++) {
     43                     int res = 0;
     44                     for (int num = 1; num <= maxi; num++) {
     45                         res = (res + pdp[maxi][remain]) % MOD;
     46                     }
     47 
     48                     if (remain > 0) {
     49                         for (int num = maxi + 1; num <= m; num++) {
     50                             res = (res + pdp[num][remain - 1]) % MOD;
     51                         }
     52                     }
     53 
     54                     dp[maxi][remain] = res;
     55                 }
     56             }
     57             pdp = dp;
     58         }
     59         return dp[0][k];
     60     }
     61 };