leetcode

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