Đề bài
Cho một số N, chúng ta phải tìm số lượng số đối xứng (palindrome) tối thiểu cần thiết để biểu diễn N dưới dạng tổng của chúng.
Nếu N = 15 thì cần 2 số đối xứng là 8 và 7.
Thuật toán
1. Tạo tất cả các số đối xứng lên đến N theo thứ tự đã sắp xếp 2. Tìm kích thước của tập con nhỏ nhất sao cho tổng của nó bằng 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; }
Kết quả
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