leetcode 343.整数拆分

思路：记忆化搜索或者动态规划

我们首先捋一下思路，而且分析最优解这一类问题，我们需要几个步骤：

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];}
};