整数拆分

给定一个正整数 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];
		        
		    }