確實是數學題，但我是用 DP 去解的
對於所有大於 6 的數字，要嘛拔 2 要嘛拔 3
意即：
res(n) = max(2 * res(n-2), 3 * res(n-3)) for all n > 6
為什麼是 6 呢？先從前面幾個數字看起：
2 -> 1 + 1, res(2) = 1
3 -> 1 + 2, res(3) = 2
4 -> 2 + 2, res(4) = 4 — 這邊如果直接代我上面的公式，會使得 4 被拆成 2+1+1
5 -> 2 + 3, res(5) = 6 — 同上，會拆出 1 來
6 -> 3 + 3, res(6) = 9 — 同上
關於這其中的道理我還不太懂，但猜想有可能是因為 6 以下的數字，2 和 3 出現的次數會
是 1 次或 0 次，沒辦法用公式解
那為什麼拔 2 或 3 就可以？往上看幾個：
拔 4 -> 等同於拔兩個 2
拔 5 -> res(5) = 6，一定小於分開拔 2 跟 3
拔 6 -> 同上，拔出來的數字會使得成績變小
…
以此類推
沒辦法給出詳細的證明，但我想 idea 差不多就這樣
Code:
class Solution:
def __init__(self):
self.table = [-1, -1, 1, 2, 4, 6, 9]
def integerBreak(self, n: int) -> int:
while n > len(self.table) - 1:
length = len(self.table)
self.table.append(max(2 * self.table[length - 2], 3 * self.table[len
gth - 3]))
return self.table[n]
Ps:
其實這題單純用遞迴解也可以，只是 Python 寫這類題目通常都會 TLE，所以我才直接用 D
P Table
可能因為這題的 n 只到 58 吧，if-else 硬幹也能過
Code:
class Solution:
def integerBreak(self, n: int) -> int:
if n == 2: return 1
elif n == 3: return 2
elif n == 4: return 4
elif n == 5: return 6
elif n == 6: return 9
else: return max(2 * self.integerBreak(n-2), 3 * self.integerBreak(n-3))
Ps2:
或你想要 fancy 一點用 match-case 也可以，意思一樣：
Code:
class Solution:
def integerBreak(self, n: int) -> int:
match n:
case 2: return 1
case 3: return 2
case 4: return 4
case 5: return 6
case 6: return 9
case _: return max(2 * self.integerBreak(n-2), 3 * self.integerBreak
(n-3))
※ 引述 《ZooseWu》 之銘言：
: 標題：Re: [閒聊] 每日LeetCode
: 時間: Fri Oct 6 15:52:22 2023
:
: ※ 引述《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
: }
:
:

大師

大師