原題鏈接：

343. 整數(shù)拆分

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

完成情況：

解題思路：

	 解題思路：
	    如何使面積最大呢？  -> 毫無疑問，肯定是正方形
	    那么每次我就嘗試以均等切分，保存當(dāng)前的合，
	    然后迭代求和最大值和最小值，產(chǎn)生一個(gè)新的均值

	 舉例：
	    10
	    5*5  ->25
	    5*3*2 ->30
	    【5和2合并再均分】
	    4*3*3  ->36
	    【4和3合并再均分】，與前面【5和2合并再均分】產(chǎn)生的合相同，故結(jié)束。
	    Max算計(jì)算過得哪個(gè)值最大。

貼一張對比數(shù)據(jù)圖，大家可以自行驗(yàn)證，是否上述規(guī)律會得到正確答案。文章來源地址http://www.zghlxwxcb.cn/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整數(shù)拆分 {
	public int integerBreak(int n) {
		//2 <= n <= 58
		//只要前一個(gè)結(jié)果，跟后一個(gè)結(jié)果有關(guān)系的題目 ，基本上都可以使用到dp
		int dp_splitMaxArea [] = new int[n+1];
		//2 <= n <= 58
		/**
		 解題思路：
		    如何使面積最大呢？  -> 毫無疑問，肯定是正方形
		    那么每次我就嘗試以均等切分，保存當(dāng)前的合，
		    然后迭代求和最大值和最小值，產(chǎn)生一個(gè)新的均值

		 舉例：
		    10
		    5*5  ->25
		    5*3*2 ->30
		    【5和2合并再均分】
		    4*3*3  ->36
		    【4和3合并再均分】，與前面【5和2合并再均分】產(chǎn)生的合相同，故結(jié)束。
		    Max算計(jì)算過得哪個(gè)值最大。
		 */
		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];
	}
}

到了這里，關(guān)于343. 整數(shù)拆分的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！