จำนวนพาลินโดรมน้อยที่สุดที่ผลรวมเท่ากับ N ด้วย C++

ข้อความโจทย์

กำหนดจำนวน N เราต้องหาจำนวนพาลินโดรม (Palindromes) น้อยที่สุดที่จำเป็นเพื่อแสดง N เป็นผลรวมของพวกมัน

ถ้า N = 15 แล้วต้องการพาลินโดรม 2 ตัวคือ 8 และ 7

อัลกอริทึม

1. สร้างพาลินโดรมทั้งหมดจนถึง N แบบเรียงลำดับ
2. หาขนาดของเซตย่อยที่เล็กที่สุดที่ผลรวมเท่ากับ N

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

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

vector<vector<long long>> table;

int createPalindrome(int input, bool isOdd) {
    int n = input;
    int palindrome = input;
    if (isOdd)
        n /= 10;
    while (n > 0) {
        palindrome = palindrome * 10 + (n % 10);
        n /= 10;
    }
    return palindrome;
}

vector<int> generatePalindromes(int n) {
    vector<int> palindromes;
    int number;
    for (int j = 0; j < 2; j++) {
        int i = 1;
        while ((number = createPalindrome(i++, j)) <= n)
            palindromes.push_back(number);
    }
    return palindromes;
}

long long minSubsetSize(vector<int>& vec, int i, int j, int n) {
    if (n == 0)
        return 0;
    if (i > j || vec[i] > n)
        return INT_MAX;
    if (table[i][n])
        return table[i][n];
    table[i][n] = min(1 + minSubsetSize(vec, i + 1, j, n - vec[i]), minSubsetSize(vec, i + 1, j, n));
    return table[i][n];
}

int requiredPalindromes(int n) {
    vector<int> palindromes = generatePalindromes(n);
    sort(palindromes.begin(), palindromes.end());
    table = vector<vector<long long>>(palindromes.size(), vector<long long>(n + 1, 0));
    return minSubsetSize(palindromes, 0, palindromes.size() - 1, n);
}

int main() {
    int n = 15;
    cout << "Minimum required palindromes = " << requiredPalindromes(n) << endl;
    return 0;
}

ผลลัพธ์

เมื่อคอมไพล์และรันโปรแกรมด้านบน จะได้ผลลัพธ์ดังนี้ -

Minimum required palindromes = 2