Số palindromes tối thiểu được yêu cầu để biểu thị N thành tổng bằng C ++.

Tuyên bố vấn đề

Cho một số N, chúng ta phải tìm số palindromes tối thiểu cần thiết để biểu thị N thành tổng của chúng

Nếu N =15 thì cần có 2 palindromes, tức là 8 và 7.

Thuật toán

1. Generate all the palindromes up to N in a sorted fashion
2. Find the size of the smallest subset such that its sum is N

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Minimum required palindromes = 2