Break Number Into 3 Parts หาผลรวมสูงสุด (DP)

กำหนดตัวเลข n ต้องการแยก n เป็น 3 ส่วน: n/2, n/3, n/4 (ปัดทศนิยมทิ้ง) แล้วหาผลรวมสูงสุดที่ได้จากการแยกซ้ำๆ จนไม่คุ้มค่าที่จะแยกต่อ

ตัวอย่าง Input และ Output

Input: n = 12
Output: Maximum sum after breaking: 13

การคำนวณ:
12 → 6+4+3 = 13 (ดีกว่า 12)
6 → 3+2+1 = 6 (เท่าเดิม หยุด)
4 → 2+1+1 = 4 (เท่าเดิม หยุด)
3 → 1+1+0 = 2 (แยกแล้วแย่กว่า หยุด)
Max = 13

อัลกอริทึม Dynamic Programming (Bottom-up)

ฟังก์ชัน maxBreakSum(n)

Recurrence:

sums[i] = max(i, sums[i/2] + sums[i/3] + sums[i/4])

ความหมาย: สำหรับตัวเลข i เราสามารถเลือกได้ 2 ทาง: - ไม่แยก: ค่า = i - แยก 3 ส่วน: ค่า = sums[i/2] + sums[i/3] + sums[i/4]

ขั้นตอน:

1. สร้างอาร์เรย์ sums[n+1]
2. sums[0]=0, sums[1]=1
3. for i = 2 ถึง n:
   • sums[i] = max(i, sums[i/2] + sums[i/3] + sums[i/4])
4. คืน sums[n]

ตัวอย่างโค้ด C++

#include <iostream>
#include <algorithm>
#define MAX 1000000
using namespace std;

int maxBreakSum(int n) {
    int sumArr[n+1];
    sumArr[0] = 0; sumArr[1] = 1;

    for (int i = 2; i <= n; i++)
        sumArr[i] = max(sumArr[i/2] + sumArr[i/3] + sumArr[i/4], i);

    return sumArr[n];
}

int main() {
    int n;
    cout << "Enter a number: "; cin >> n;
    cout << "Maximum sum after breaking: " << maxBreakSum(n);
    return 0;
}

Output

Enter a number: 12
Maximum sum after breaking: 13

ความซับซ้อน

• Time: O(n)
• Space: O(n)

เวอร์ชัน Recursive + Memoization (สำหรับ n ใหญ่มาก)

unordered_map memo;
long long maxBreakSumRec(long long n) {
    if (n <= 1) return n;
    if (memo.count(n)) return memo[n];
    return memo[n] = max(n, maxBreakSumRec(n/2) + maxBreakSumRec(n/3) + maxBreakSumRec(n/4));
}

เหมาะสำหรับ n ที่ใหญ่มาก (เช่น 10¹⁰) ที่ไม่สามารถสร้างอาร์เรย์ขนาด n ได้