leetcode

Solution to some Leetcode problems written in C++

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

1420.cpp (1744B)

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