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

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 n 不小于 2 且不大于 58。

这和《零钱兑换》那道题是同种类型，都是通过动态规划进行整数拆分，不过那道题是为找零，这道是为了求乘积。

本来，同种类型的题是不应该再记录的，但我想起当初被《零钱兑换》支配的恐惧，所以还是把这道题记录下来

思路：

dp[n]是整数n拆分后整数的最大乘积（或者叫拆n），记dp[0]=1,dp[1]=1,dp[2]=1（不解释）；

（1）下面罗列的拆分方法不列举n个1相乘的情况

①拆3：一种,1和2，所以dp[3]=2;

②拆4：三种，即1*3，2*2和1*2*1。

但是由于2又可以拆分成1和1，所以其实1*2*1与2*2可以合并成同一种类型，

所以拆4可以表示为两大类型：拆1和拆3（dp[1]*dp[3]），拆2和拆2（dp[2]*dp[2]），选出最大即可

③拆5：1*4，2*3，1*2*2，1*1*1*2，1*1*3

同理，因为4可以拆成2和2，1和3；3可以拆成1和2，2可以拆成1和1，

所以拆5可以也可以表示为两大类型：dp[1]*dp[4]，dp[2]*dp[3]，选出最大即可

④拆6：1*5，2*4，3*3，1*4*1，1*3*1*1，1*2*2*1，1*1*1*2

不必说：5可以拆成3和2,1和4；4可以拆成2和2，3可以拆成1和2，2可以拆成1和1

所以拆6可以表示为3大类型：dp[1]*dp[5]，dp[2]*dp[4]，dp[3]*dp[3],再选最大。。。

（2）说了这么多，想必都可以看出来了，

数字n拆分成整数的最大乘积是从

dp[1]*(n-1)，dp[2]*(n-2)，dp[3]*[n-3] 。。。 dp[n-1]*(1)        这些数字里面选出来的，所以代码如下：

class Solution {
    public int integerBreak(int n) {
        if(n==2){
            return 1;
        }
        if(n==3){
            return 2;
        }
        int dp[]=new int[n+2];
        dp[0]=1;dp[1]=1;dp[2]=1;
        for(int i=2;i<=n+1;++i){
            for(int j=1;j<=i;++j){
                int d=dp[j]*(i-j);
                if(d>dp[i]){
                    dp[i]=d;
                }
            }
        }
        return dp[n+1];
    }
}

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

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

思路：

1.使用递归的思想，将n拆分成i和n-i   可以得到一个积  然后对n-i进行递归

    //利用递归的思想 
	//从1开始遍历，在res,i*(n-i)-->就是说一个数n只拆分一次即i和n-i来比较一下，还有就是对n-i再继续拆分
	public int integerBreak(int n) {
		if(n==1) return 1;
		int res=Integer.MIN_VALUE;
		for (int i = 1; i < n; i++) {
			res=Math.max(res, Math.max(i*(n-i), i*integerBreak(n-i)));
		}
		return res;      
    }

2.还是递归的思想  不过对代码进行记忆化搜索，加入到map中

       //记忆化搜索
	   //利用递归的思想 
	    HashMap<Integer, Integer> map=new HashMap<>();
		public int integerBreak1(int n) {
			if(n==1) return 1;
			 if(map.containsKey(n)){ //看map是否包含  之前是否计算过
		            return map.get(n);
		        }
			int res=Integer.MIN_VALUE;
			for (int i = 1; i < n; i++) {
				res=Math.max(res, Math.max(i*(n-i), i*integerBreak1(n-i)));
			}
			将每次递归结束后的值存储一下
			map.put(n, res);
			return res;      
	    }

3.暴力递归改动态规划

         //动态规划
		 public static int integerBreak3(int n) {
		        int[] dp = new int[n+1];
		        dp[1] = 1;
		        for(int i=2;i<=n;i++){
		            for(int j=1;j<i;j++){
		            	System.out.println(dp[i]);
		                dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
		            }
		        }
		        return dp[n];
		        
		    }