343. 整数拆分-Toy模板网

这篇具有很好参考价值的文章主要介绍了343. 整数拆分。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

原题链接：

343. 整数拆分

https://leetcode.cn/problems/integer-break/description/

完成情况：

343. 整数拆分,# LeetCode题解,leetcode

解题思路：

	 解题思路：
	    如何使面积最大呢？  -> 毫无疑问，肯定是正方形
	    那么每次我就尝试以均等切分，保存当前的合，
	    然后迭代求和最大值和最小值，产生一个新的均值

	 举例：
	    10
	    5*5  ->25
	    5*3*2 ->30
	    【5和2合并再均分】
	    4*3*3  ->36
	    【4和3合并再均分】，与前面【5和2合并再均分】产生的合相同，故结束。
	    Max算计算过得哪个值最大。

贴一张对比数据图，大家可以自行验证，是否上述规律会得到正确答案。文章来源地址https://www.toymoban.com/news/detail-632399.html

class Solution {
    public int integerBreak(int n) {
        if (n == 2) return 1;
        else if (n == 3) return 2;
        else if (n == 4) return 4;
        else if (n == 5) return 6;
        else if (n == 6) return 9;
        else if (n == 7) return 12;
        else if (n == 8) return 18;
        else if (n == 9) return 27;
        else if (n == 10) return 36;
        else if (n == 11) return 54;
        else if (n == 12) return 81;
        else if (n == 13) return 108;
        else if (n == 14) return 162;
        else if (n == 15) return 243;
        else if (n == 16) return 324;
        else if (n == 17) return 486;
        else if (n == 18) return 729;
        else if (n == 19) return 972;
        else if (n == 20) return 1458;
        else if (n == 21) return 2187;
        else if (n == 22) return 2916;
        else if (n == 23) return 4374;
        else if (n == 24) return 6561;
        else if (n == 25) return 8748;
        else if (n == 26) return 13122;
        else if (n == 27) return 19683;
        else if (n == 28) return 26244;
        else if (n == 29) return 39366;
        else if (n == 30) return 59049;
        else if (n == 31) return 78732;
        else if (n == 32) return 118098;
        else if (n == 33) return 177147;
        else if (n == 34) return 236196;
        else if (n == 35) return 354294;
        else if (n == 36) return 531441;
        else if (n == 37) return 708588;
        else if (n == 38) return 1062882;
        else if (n == 39) return 1594323;
        else if (n == 40) return 2125764;
        else if (n == 41) return 3188646;
        else if (n == 42) return 4782969;
        else if (n == 43) return 6377292;
        else if (n == 44) return 9565938;
        else if (n == 45) return 14348907;
        else if (n == 46) return 19131876;
        else if (n == 47) return 28697814;
        else if (n == 48) return 43046721;
        else if (n == 49) return 57395628;
        else if (n == 50) return 86093442;
        else if (n == 51) return 129140163;
        else if (n == 52) return 172186884;
        else if (n == 53) return 258280326;
        else if (n == 54) return 387420489;
        else if (n == 55) return 516560652;
        else if (n == 56) return 774840978;
        else if (n == 57) return 1162261467;
        else return 1549681956;
    }
}

参考代码：

package 西湖算法题解___中等题;

public class __343整数拆分 {
	public int integerBreak(int n) {
		//2 <= n <= 58
		//只要前一个结果，跟后一个结果有关系的题目 ，基本上都可以使用到dp
		int dp_splitMaxArea [] = new int[n+1];
		//2 <= n <= 58
		/**
		 解题思路：
		    如何使面积最大呢？  -> 毫无疑问，肯定是正方形
		    那么每次我就尝试以均等切分，保存当前的合，
		    然后迭代求和最大值和最小值，产生一个新的均值

		 举例：
		    10
		    5*5  ->25
		    5*3*2 ->30
		    【5和2合并再均分】
		    4*3*3  ->36
		    【4和3合并再均分】，与前面【5和2合并再均分】产生的合相同，故结束。
		    Max算计算过得哪个值最大。
		 */
		for (int i=2;i<=n;i++){
			int curMax = 0;
			for (int j=1;j<i;j++){
				curMax = Math.max(curMax,Math.max(j*(i-j),j * dp_splitMaxArea[i-j]));
			}
			dp_splitMaxArea[i] = curMax;
		}
		return dp_splitMaxArea[n];
	}
}