动态规划——343. Integer Break［Medium］

动态规划——343. Integer Break［Medium］

题目描述

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).

Note: You may assume that n is not less than 2 and not larger than 58.

解题思路

经过观察，我发现这是一个  可重复背包  问题：

给定的数  n  就是容器体积，拆分出来的数字个数  就是  要选择的商品种类。然后，因为 4 ＝ 2+2，可以选择2个2，因此，同种商品数量不限。

result［j］：当数字为j时所能得到的最大乘积。

result［j］ ＝ max（result［j］，result［j － o］＊o）：不放入这种商品和放入这种商品，两者最大值。

／／因为是乘积，因此初始化应该为1，不能为0；

代码如下

class Solution {
public:int integerBreak(int n) {vector<int> result(n + 1, 1);
for (int o = 1; o < n; o++) {for (int j = 1; j < result.size(); j++) {if (o > j) continue;result[j] = fmax(result[j], result[j - o] * o);}}return result[n];
}
};