ปัญหา
กำหนดจำนวนเต็ม n หาตัวเลข ≥ 2 ตัวที่ผลรวม = n ให้ product สูงสุด
ตัวอย่าง: n=12 → 81 (3+3+3+3=12, 3×3×3×3=81)
วิธีแก้: Dynamic Programming
DP Recurrence
dp(n) = max product สำหรับ n
dp(0) = 1 (base case สำหรับการคูณ)
dp(n) = max(i × dp(n-i)) สำหรับ i = 1..n
โค้ด Python (Top-down DP)
class Solution:
def solve(self, n):
def dp(n):
if n == 0:
return 1
ans = 0
for i in range(1, n + 1):
ans = max(ans, i * dp(n - i))
return ans
return dp(n)
# ทดสอบ
ob = Solution()
print(ob.solve(12)) # 81
print(ob.solve(10)) # 36 (3+3+4 or 3+3+2+2)
print(ob.solve(2)) # 1 (1+1)
print(ob.solve(3)) # 2 (1+2)
Mathematical Solution (Optimal)
โจทย์นี้เป็น "Integer Break" (LeetCode 343) มีคำตอบทางคณิตศาสตร์:
- แยกเป็น 3 มากที่สุด
- ถ้าเหลือ 1: เปลี่ยน 3+1 → 2+2 (เพราะ 3×1 < 2×2)
- ถ้าเหลือ 2: คง 2 ไว้
O(1) Formula
def integerBreak(self, n):
if n <= 3:
return n - 1
if n % 3 == 0:
return 3 ** (n // 3)
if n % 3 == 1:
return 3 ** (n // 3 - 1) * 4
return 3 ** (n // 3) * 2 # n % 3 == 2
# ทดสอบ
for n in range(2, 20):
print(f"n={n}: {integerBreak(n)}")
ความซับซ้อน
| วิธี | Time | Space |
|---|---|---|
| DP Recursive (no memo) | O(2ⁿ) | O(n) |
| DP Bottom-up / Memoized | O(n²) | O(n) |
| Mathematical | O(1) | O(1) |
ทำไม 3 เป็น optimal?
ฟังก์ชัน f(x) = (n/x)^x สูงสุดที่ x = e ≈ 2.718 → จำนวนเต็มใกล้สุดคือ 3
DP Bottom-up Version
def solve_dp(self, n):
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for j in range(1, i + 1):
dp[i] = max(dp[i], j * dp[i - j])
return dp[n]
