思路：记忆化搜索或者动态规划
我们首先捋一下思路，而且分析最优解这一类问题，我们需要几个步骤：
1.看问题的描述，找出问题问的最优问题是什么；
2.然后我们就模拟一下这个问题进行到最后一步是什么样子；
3.去掉最后一步又是什么样子；
4.照着2.3步一直类推，这就是递推的过程，也就是我们需要模拟的过程。
举个例子，就拿这道题来说，最优问题是：把一个数拆开k个，使其乘积最大。
进行到最后一步时，是拆出的所有数进行相乘，得出最大乘积；
那么我们去掉最后一步时，其实就是把其中的两个数合起来，这个时候是最后一步的前一步。
这只类推，直到推到所给的n数。
就是这么一个过程。可能有点抽象，那么就先看记忆化搜索的代码，其实也就是DFS：
int mem[100];
class Solution {
public:
int dfs(int u){
if(mem[u])return mem[u];
if(u==0)
return 1;
else{
int res=0;
for(int i=1;i<u;i++){
res=max(res,max(i*(u-i),dfs(u-i)*i));
}
return mem[u]=res;
}
}
int integerBreak(int n) {
return dfs(n);
}
};好了，剩下的DP其实就是对于上面的这个递推进行了改写而已，dfs改写成dp数组就行了。由于dfs中的u也在变化，其中的拆分数也在变化，所以需要两个循环进行改写。
上代码：
class Solution {
public:
int integerBreak(int n) {
vector<int>dp(n+1);
int res=0;
for(int i=2;i<=n;i++){
res=0;
for(int j=1;j<i;j++){
res=max(res,max(j*(i-j),dp[i-j]*j));
}
dp[i]=res;
}
return dp[n];
}
};
