※ 引述《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
}