确实是数学题，但我是用 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
: }
:
: