/**
1、确定dp数组(dp table)以及下标的含义
2、确定递推公式
3、dp数组如何初始化
4、确定遍历顺序
5、举例推导dp数组
给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
2 <= n <= 58
1、dp[n]表示
2、dp[n] =
3、 dp[2] = 1+1; 1*1 = 1
dp[3] = 1+2; 1*2 = 2
dp[4] = 2+2; 2*2 = 4
dp[5] = 2+3; 2*3 = 6
dp[6] = 3+3; 3*3 = 9
dp[7] = 3+4; 3*4 = 12
dp[8] = 2+3+3; 2*3*3 = 18
dp[9] = 3+3+3; 3*3*3 = 27
dp[10] = 3+3+4; 3*3*4 = 36
dp[11] = 3+3+3+2; 3*3*3*2 = 58
dp[12] = 3+3+3+3; 3*3*3*3 = 81
dp[13] = 3+3+3+4; 3*3*3*4 = 108
4、从左上到右下
5、同3
*/
function main(n) {
const dp = [1,2,4,6]
if(n<=5) return dp[n-2]
const count = parseInt(n / 3)
const a = n % 3
switch(a) {
case 0:
return Math.pow(3, count)
case 1:
return Math.pow(3, (count -1)) * 4
case 2:
return Math.pow(3, count) * 2
}
}
console.log(main(13))
// 时间复杂度:O(1)
// 空间复杂度:O(1)