※ 引述《yam276 (史莱哲林的优等生)》之铭言：
: 343. Integer Break
: 把整数拆成相加的数字
: 取这些数字最大乘积
这题我是以递回的思路去想的
对于任意数x 他拆分后的最大乘积res(x)
res(x)=res(x1)*res(x2) (x1+x2=x)
不会证明
乘法有结合律
想一下应该能得出这个结论
所以每个数都可以拆成更小的两个数找最大乘积
我们只要找到递回的终点就能知道怎么反推回来
2=>2
3=>3
4=>4
5=>3*2
6=>3*3
能够知道最小拆分就是3 能拆越多3就越大
然后4是例外 2*2>3*1
除此之外还题目还限制每个数字至少要拆成两个数
所以2跟3会有特殊解1跟2
code:
function integerBreak (n: number): number {
if (n === 2) return 1 //特殊解
else if (n === 3) return 2 //特殊解
let result = Math.pow(3, Math.floor(n / 3)) //计算有几个3
if (n % 3 === 1) result *= 4 / 3 //最后是4 要少拆一次3
else if (n % 3 === 2) result *= 2
return result
}