本文主要是介绍阿亮的算法之路——343整数拆分,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
动态规划集中练习
题目详情
自己思考
看到这个题目,会想到用动态规划来做,但是我在想,可不可以用一种统一的思想来解决这个问题呢?类似的,比如给定一个周长,求围成面积最大的图形,那一定是园,将各个方向都崩得最大。
我觉得这个题和求面积最大的图形那个题很类似,那这个题的思路肯定也是,将拆分的个数和每一个数的大小都要最大。经过多次尝试,都不行,因为,要拆分成整数,就无法很好的同时兼顾,比如10,按照我的思路,就是应该拆分成3、3、3、1,但是应该是拆成2、3、2、3才是最优的解。而且,应该因数的个数和因数的大小权重应该是不一样的。
第一次
思路
如果用动态规划,这个题实际上有几个弯需要转。
首先就是,状态转移方程应该怎么写,
dp[i] = max(dp[m]*dp[i-m]) m=1,2,3……i-1。我想到的动态转移方程也是这样,比如说10 = 2、3、2、3,就是10 = 5、5,那dp[5]呢?5 = 2、3。但是,dp[2]和dp[3]呢,dp[2] = 1,dp[3] = 2。
所以,对于1,2,3,这个三个特殊的数字,不能把它们的结果放入dp中,而需要特殊判断,特殊返回。如果想要后面的结果正确。那么dp[2]就应该是2,而不是需要返回的1,同样dp[3]应该是2。
另外,如果是完全平方数的整数倍,那么一定是按照完全平方数来拆的。比如dp[8] = dp[4] * dp[4]。dp[27] = dp[9] *dp[9] *dp[9]
代码
public static int integerBreak(int n){if (n==1) return 1;if (n==2) return 1;if (n==3) return 2;int[] dp = new int[n+1];if (n /(int)Math.sqrt(n) == 0){dp[n] = (int)Math.pow((int)Math.sqrt(n),n /(int)Math.sqrt(n));return (int)Math.pow((int)Math.sqrt(n),n /(int)Math.sqrt(n));}dp[1] = 1;dp[2] = 2;dp[3] = 3;for (int i = 3; i <= n; i++){for (int j = i/2; j >= 1; j--){ dp[i] = dp[i] > dp[j] *dp[i-j]?dp[i] : dp[j] *dp[i-j]; }}return dp[n];}
主要就是1、2、3这三个特殊的数字,需要特殊处理。
提交结果
哈哈,我感觉还不错。
第二次
稍微的对完全平方数的整数倍那里优化了一下
public static int integerBreak(int n){if (n==1) return 1;if (n==2) return 1;if (n==3) return 2;int[] dp = new int[n+1];int sqrt = (int)Math.sqrt(n);if (n /sqrt == 0){dp[n] = (int)Math.pow(sqrt,n /sqrt);return (int)Math.pow(sqrt,n /sqrt);}dp[1] = 1;dp[2] = 2;dp[3] = 3;for (int i = 3; i <= n; i++){for (int j = i/2; j >= 1; j--){ dp[i] = dp[i] > dp[j] *dp[i-j]?dp[i] : dp[j] *dp[i-j]; }}return dp[n];}
提交结果
bingo!!
这篇关于阿亮的算法之路——343整数拆分的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!