343.整数拆分
刷题刷题找工作！
题目链接
DP入门之整数拆分！
题目：
给定一个正整数
n，将其拆分为k个 正整数 的和（k >= 2），并使这些整数的乘积最大化。返回 你可以获得的最大乘积 。
自己的思路
。。。完全不会做
官方题解
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n + 1);
dp[2] = 1;
for (int i = 3; i <= n ; i++) {
for (int j = 1; j < i - 1; j++) {
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
}
}
return dp[n];
}
};为什么是两层for循环，因为每一个dp[i]都要慢慢拆成几个数，你可以理解一下，已经算到i了，所以后面的什么dp[j],dp[i-j]都已经获得了，就是在求最大值了，为什么会需要取dp[i]max一下，毕竟有的那么多的循环啊，要取一个和为最大的才能当作它的最终结果，好了理解了。
再问，为什么j<i-1,因为i-j的差距至少为2，dp[0]和dp[1]是无意义的。
再问，为什么拆分更好分成这两个？因为dp[i-j]的拆分数量是一定大于2个的，所以要把只拆分一个，即不拆分的单独提出来（之前写得，现在看不懂这句话了）
注意，max只有两个参数，写成这样三个会报错？是的，所以它是写成两个max来找最大