leetcode

0 // DP

1 class Solution {

2 static int dp[64];

3

4 int rec(const int n) const {

5 if (n <= 3) return n;

6 if (dp[n] != -1) return dp[n];

7 int res = n;

8 for (int i = 2; i < n; i++)

9 res = max(res, i * rec(n - i));

10 return dp[n] = res;

11 }

12

13 public:

14 Solution() { memset(dp, 0xFF, sizeof(dp)); }

15 int integerBreak(const int n) const {

16 if (n <= 3) return n - 1;

17 return rec(n);

18 ;

19 }

20 };

21

22 int Solution::dp[64];