343. Integer Break
Đề Bài
Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers.
Return the maximum product you can get.
Example 1:
Input: n = 2 Output: 1 Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: n = 10 Output: 36 Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Constraints:
2 <= n <= 58
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n)
💾 Không gian
O(n)
Lời Giải
C++
0343-integer-break.cpp
int memo[59][59][59];
class Solution {
private:
int n;
public:
int dp(int i, int s, int c) {
if (s == 0) {
return c > 1;
}
if (s < 0 or i > n) {
return 0;
}
if (memo[i][s][c] != -1) {
return memo[i][s][c];
}
int ans = 0;
for (int j = i; j <= n; ++j) {
ans = max(ans, j*dp(j, s - j, c + 1));
}
return memo[i][s][c] = ans;
}
int integerBreak(int n) {
this->n = n;
memset(memo, -1, sizeof(memo));
return dp(1, n, 0);
}
};