光谷做网站,住房和城乡建设部网站一级建造师,网站设计的时间计划,申请网页空间在本题目中#xff0c;我们需要拆分一个整数n#xff0c;让其拆分的整数积最大。因为每拆分一次都和之前上一次拆分有关系#xff0c;比如拆分6可以拆成2x4#xff0c;还可以拆成2x2x2#xff0c;那么我们可以采用动态规划来做。
首先确定dp数组的含义#xff0c;这里dp… 在本题目中我们需要拆分一个整数n让其拆分的整数积最大。因为每拆分一次都和之前上一次拆分有关系比如拆分6可以拆成2x4还可以拆成2x2x2那么我们可以采用动态规划来做。
首先确定dp数组的含义这里dp[i]表示将i拆分之后所得的乘积为dp[i]。
然后确定递推公式这里我们要思考我们是要把i拆成若干个数然后相乘取最大值也就是说我们需要Math.max()。我们继续思考如果拆成两个数那就是把i拆成j和i-j这两个数的乘积就是j*(i-j)。如果拆成三个或者四个或者更多我们可以表示成jdp[i-j]。因为我们dp数组的定义就是把i-j拆成若干结果乘积最大。但我们还需要考虑在我们拆之前dp[i]这个数的大小因为当我们开始遍历的时候i是一个数字那么我们就要考虑这个dp[i]。比如我们要拆dp[10]加入在拆到dp[6]的时候获得了最大值那么之后我们直接把410-6直接拆成4个1即可。所以我们也要加入dp[i]。同时我们只需要拆i就可以了不需要拆j了如果我拆j的效果其实是和拆i-j一样的比如把6拆成4x2或者2x4二者结果是一致的。所以递推公式应该是Math.max(dp[i],Math.max(j(i-j),j*dp[i-j]))。
然后我们进行初始化题中说明n是正整数所以dp[0]没有意义。dp[1]无法拆成两个正整数的和所以也没有意义dp[2] 1。
然后确定遍历顺序这里我们是要先遍历i然后在i确定的基础上再把i进行拆分然后再遍历j即可。
打印数组
class Solution {public int integerBreak(int n) {//dp[i] 为正整数 i 拆分后的结果的最大乘积int[] dp new int[n1];dp[2] 1;for(int i 3; i n; i) {for(int j 1; j i-j; j) {// 这里的 j 其实最大值为 i-j,再大只不过是重复而已//并且在本题中我们分析 dp[0], dp[1]都是无意义的//j 最大到 i-j,就不会用到 dp[0]与dp[1]dp[i] Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));// j * (i - j) 是单纯的把整数 i 拆分为两个数 也就是 i,i-j 再相乘//而j * dp[i - j]是将 i 拆分成两个以及两个以上的个数,再相乘。}}return dp[n];}
}
