给定一个正整数n,将其拆分为至少两个正整数的和,
并使这些整数的乘积最大化。返回你可以获得的最大乘积
目前只想到了贪心算法,和动态规划
贪心算法判断3的连乘 例如
7 34
12 3333
1.贪心算法
/*
* @params number
* @return number
*/
var Integer1 = (number) => {
//
if(number<=3)return number
let sum = Math.floor(number/3)
let remainder = number % 3
if(remainder == 2){
return 3 ** sum * 2
}else if(remainder ==1){
return 3 ** (sum-1) * 4
}
}
2.动态规划
/*
* @params number
* @return number
*/
var Integer3 = (n)=>{
const dp =new Array(n+1).fill(1)
for(var i = 3; i<= n;i++){
for(var j = 0;j<i;j++){
dp[i] = Math.max(dp[i],j*(i-j),j*dp[i-j])
}
}
return dp[n]
}
动态规划的思想就是,把整数拆分若干个数,然后用这些数字拆分为两个数字相乘
最后在相乘比较。