神刀安全网

Dynamic Programming – Integer Break

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get. For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

We can useDynamic Programming (DP) to solve this problem. The puzzle does not ask you exactly how to break the integer. If we use f(n) to denote that the maximum product to break the integer n, then we have the following recurrence formula:

Dynamic Programming – Integer Break

for Dynamic Programming – Integer Break

.

If we break the integer i-j, the intermediate result is f(i-j) otherwise we have to check if we break i into i-j and j. The time complexity is O(n^2) and the space complexity is O(n).

class Solution { public:     int integerBreak(int n) {         vector<int> f(n + 1, 0);         f[1] = 0;         f[2] = 1;         for (int i = 2; i < n + 1; i ++) {             for (int j = 1; j < i; j ++) {                 f[i] = max(f[i], max(i - j, f[i - j]) * j);             }         }         return f[n];     } };
class Solution { public:     int integerBreak(int n) {         vector<int> f(n + 1, 0);         f[1] = 0;         f[2] = 1;         for (int i = 2; i < n + 1; i ++) {             for (int j = 1; j < i; j ++) {                 f[i] = max(f[i], max(i - j, f[i - j]) * j);             }         }         return f[n];     } };

–EOF–

GD Star Rating

loading…

297 words

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » Dynamic Programming – Integer Break

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址