343.整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

分析：这道题可以用两种方法做，第一种是贪心，第二种是动态规划，相对来说，贪心更好理解一些。
方法一（贪心算法）：
对于整数拆分，拆出3这个数会使结果最大，2其次，不要拆出5和1这种数
参考代码：
public int integerBreak(int n) {
if(n==2) return 1;
if(n==3) return 2;
if(n==4) return 4;
int ret=1;
while(n>4){
ret=3;
n-=3;
}
ret=n;
return ret;
}
方法二（动态规划）：
动态规划的思路还是比较难想的，还是用贪心方便
第一步：dp[i]代表什么？答：表示数为i的时候拆分的最大值
第二步：如何获得？有两种获得方式，取最大的：1.dpi,一个是j*dp[i-j]}即一个是拆分成两个数，j和i-j，一个将其拆分成多个，j和多个i-j；

第三步：初始化？答：初始化第二个即可
public int integerBreak(int n) {
int[] dp = new int[n+1];
dp[2]=1;
for(int i=3;i<=n;i++){
for(int j=1;j dp[i]=Math.max(dp[i],Math.max(j(i-j),jdp[i-j]));
}
}
return dp[n];
}