说是每日一道算法，最后间隔了将近三个月才继续
也是本人确实懒怠了，拿到offer之后gap了一段时间。可以gap，但是不要懒怠。保持热爱，追逐想要东西
1.题目描述
链接：https://leetcode.cn/problems/integer-break/description/
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积
示例：
2.题目解析
这道题之前做过，但是二刷还是倒下了，进行再次解析
这是一道很经典的动态规划题目，怎么想到动态规划呢？n 的 取值依赖前面 [1,n-1]的取值
动态数组
设数组 dp，dp[i]表示正整数i拆分后的最大乘积值
状态转移
难点在于状态转移的分析，i 可以拆分为 多个数字，那么我们可以取其中一个数字作为基底，其他数字组合作为一种拆分，那么
dp[i] = max(j * dp[i-j], j * (i-j))。我们遍历 j 从 [1,i-1] 是不是就能所有可能的解了。
这里为什么j不进行拆分，j 拆分其实也可以的，但是相当于重复计算了，假设 j 也拆分了，那么是不是同样我们还是 可以取一个 数字，剩下的所有数字可以认为是 dp[k]的拆分（这里 k 举个例子）
从这个分析我们可以得到一个简单的版本，也就是二重遍历，遍历 i 从 [1,n]，遍历 j 从 [1,i-1]
优化
我们不妨进行进一步优化，分析不同的情况；这里假设了 i ＞ 4 ，i ≤ 4 直接返回即可
对 j 进行分析：
j ≥ 4 时，j 是不是可以拆分为 2 + (j-2) ➡️ 2 * (j-2) = 2 * j -4 ≥ j ，当且仅当 j=4时等号成立
那么，对于 j >= 4的情况我们是不需要去考虑的，因为他一定不是最大的（j继续拆分会得到更大的）
j =1 时，dp[i] >= max(dp[i-1], i- 1)。任何一个数字都可以加上 1 使得乘积更大，dp[i-1]拆分后的任何一个数字 + 1 都会得到更大的乘积，因此 j =1 也不需要考虑
例如 i =5 , (i-1) * 1很小，dp[4] = 4; 不如把 1 加到其中一个数字上，例如 2，则得到 dp[5] = 6
综上，我们只需要考虑 j = 2 和 j = 3的情况即可
代码实现
优化版本：
class Solution {
public:
int integerBreak(int n) {
vector<int>dp{ 0,0,1,2,4 };
if (n <= 4)
return dp[n];
dp.resize(n + 1);
for (int i = 5; i <= n; ++i)
{
dp[i] = max(2 * max(dp[i - 2], i - 2), 3 * max(dp[i - 3], i - 3));
}
return dp[n];
}
};