การแยกจำนวนเต็มเพื่อหาผลคูณสูงสุดใน C++

ให้จำนวนเต็มบวก n แยกเป็นผลรวมของจำนวนเต็มบวกอย่างน้อย 2 จำนวน เพื่อให้ ผลคูณสูงสุด

ตัวอย่าง: n=10 → 36 (10 = 3+3+4, 3×3×4=36)

ขั้นตอนการแก้ปัญหา (DP / Mathematical)

วิธี DP (Top-down with memo):

1. ฟังก์ชัน solve(n, dp, flag):
   • flag = true หมายถึงการเรียกครั้งแรก (ต้องแยกอย่างน้อย 2 จำนวน)
   • ถ้า n == 0 → 1 (neutral element ของการคูณ)
   • ถ้า memo มี → คืน
   • end = flag ? n-1 : n (ครั้งแรกห้ามใช้ n เอง)
   • วน i = 1..end หา max(i * solve(n-i, dp, false))
2. คำตอบ = solve(n, dp, true)

หมายเหตุ: สูตรทางคณิตศาสตร์ ใช้ 3 ให้มากที่สุด (3×3 > 2×2×2, 3×1 < 2×2) เร็วกว่า DP

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

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(int n, vector<int>& dp, bool flag = true) {
        if (n == 0) return 1;
        if (dp[n] != -1) return dp[n];
        int end = flag ? n - 1 : n;
        int ret = 0;
        for (int i = 1; i <= end; i++) {
            ret = max(ret, i * solve(n - i, dp, false));
        }
        return dp[n] = ret;
    }
    int integerBreak(int n) {
        vector<int> dp(n + 1, -1);
        return solve(n, dp);
    }
};

int main() {
    Solution ob;
    cout << ob.integerBreak(10);
}

Input

10

Output

36