-> https://hotavn.com/quy-hoach-dong-dpcntpalin-phan-tich-chuoi-thanh-palindrom_103173.html?group=7

Nhận xét:

• Đối với quy hoạch động, ta sẽ dựa trên kết quả của các bài toán con đã tính được từ trước, tức là chỉ cần tính được phần tử đang xét từ các phần tử đã tính được từ trước trong mảng và cứ thế lặp lại từ bài toán đơn giản đến bài toán lớn thoả mãn yêu cầu bài toán.
• Gọi là số palindrome ít nhất phân tích được của i chữ cái đầu tiên của xâu , ta có một số trường hợp như sau:
  • vì chỉ có kí tự.
  • Ta tách kí tự kể từ của xâu thành kí tự đầu tiên và kí tự thứ , khi đó số palindrome phân tích được là:
  • Ta xét kí tự thứ , nếu và các kí tự kể từ cho đến hợp lại thành một chuỗi palindrome thì ta có số palindrome ít nhất phân tích được là: , trong đó là số palindrome ít nhất phân tích từ kí tự đầu tiên của xâu , ta cộng thêm bởi thêm một palindrome (đống kí tự từ cho đến ).
• Tóm lại, ta có công thức QHĐ:

Hàm kiểm tra palindrome

bool check(int L, int R){ 
    string s1 = "", s2 = "";
    for (int i = L; i<= R; i++)
        s1 = s1 + s[i];
    for (int i = R; i >= L; i--)
        s2 = s2 + s[i];
    if (s1 == s2) return true;
    else return false;
}

Giải thích

• Ta kiểm tra palindrome đúng như theo đầu bài.

Full code

#include <bits/stdc++.h>
#define MAX 100004
#define INF (int)(1e9)
#define pii pair<int, int>
#define piii pair<int, pii>
using namespace std;
char s[258];
int f[258];
int n;
bool check(int L, int R){
    string s1 = "", s2 = "";
    for (int i = L; i<= R; i++)
        s1 = s1 + s[i];
    for (int i = R; i >= L; i--)
        s2 = s2 + s[i];
    if (s1 == s2) return true;
    else return false;
}
int main()
{
    scanf("%s", s + 1); //Đọc dữ liệu vào mảng char, bắt đầu từ 1
    n = strlen(s + 1); //Lấy độ dài của mảng, tính từ 1
    f[1] = 1;


    for (int i = 2; i<=n; i++) {
        f[i] = f[i-1] + 1;
        for (int j = i-1; j>= 1; j--)
            if (s[i] == s[j])
                if (check(j + 1, i - 1) == true)
                    f[i] = min(f[i], f[j-1] + 1);
    }
    cout << f[n];
    return 0;
}

Cải tiến

-> https://hotavn.com/cai-tien-thuat-toan-bai-tap-dpcntpalin-phan-tich-chuoi-thanh-palindrom_103182.html

Nhận xét:

• Như trong bài trước, ta sử dụng công thức QHĐ và hàm kiểm tra palindrome để giải quyết bài toán. Tuy nhiên, với việc độ dài xâu lớn hơn cỡ kí tự, ta cần tìm một thuật kiểm tra palindrome hiệu quả hơn (làm giảm số vòng lặp lồng nhau).
• Ta thấy mỗi xâu palindrome có thể chia ra làm hai loại:
  • Loại 1: Xâu palindrome có "tâm" là kí tự, ví dụ: "aba", "acbca", "sbobs". Xâu "aba" có tâm là "b", xâu "acbca" có tâm là "b".
  • Loại 2: Xâu palindrome có "tâm" là kí tự, ví dụ: "baab", "cc", "rbaabr", "hotavnnvatoh". Xâu "baab" có tâm là "aa", xâu "cc" có tâm là "cc".
• Các palindrome đều có các kí tự con đối xứng nhau qua tâm của chúng, ví dụ như xâu "hotavnnvatoh" có tâm là "nn", kí tự "v", "a", "t", "o", "h", đều có các kí tự giống chúng ở phía bên kia tâm đối xứng.
• Bằng nhẫn xét trên, ta có thể thiết lập một mảng hai chiều kiểu bool có chỉ số thể hiện rằng liệu tổng của các kí tự từ tới có là palindrome không, điều kiện để tổng các kí tự từ đến là một palindrome là tổng các kí tự từ đến là palindrome và kí tự thứ và kí tự thứ phải bằng nhau.

Xây dựng mảng kiểm tra:

for (int i = 1; i<=n; i++) {
        palin[i][i] = true;
        int left = i - 1, right = i + 1;
        while (left != 0 && right != n + 1) //Điều kiện đảm bảo left và right không bị chệch ra khỏi xâu
        if (s[left] == s[right]) { 
            palin[left][right] = true;
            left--;
            right++;
        }
        else break;
        if (s[i] == s[i+1]) { //Điều kiện xâu phải có tâm là 2 kí tự
            palin[i][i+1] = true; //Hiển nhiên, tâm là một palindrome
            left = i - 1; 
            right = i + 2;
            while (left >= 1 && right <= n) { //Điều kiện đảm bảo left và right không bị chệch ra khỏi xâu
                if (s[left] == s[right]) { //Kiểm tra 2 kí tự, nếu bằng nhau thì ghi lại kết quả
                    palin[left][right] = true;
                    left--; //Nếu là palindrome thì ta xét tiếp các xâu to hơn
                    right++;
                } else break; //Nếu không bằng nhau tức là tổng các kí tự từ left tới right không phải palindrome, kết thúc vòng lặp bởi                  //nếu xét xâu sau thì điều kiện không được thoả mãn 
            }

        }
    }

Giải thích:

• Mảng hai chiều ghi lại kết quả kiểm tra xem tổng các kí tự từ tới có phải palindrome không, nếu là palindrome thì trả về , nếu không thì trả về .
• Sau khi đã xây dựng được mảng kiểm tra, ta chỉ cần lắp lại vào thuật toán cũ là xong.

Full code:

#include <bits/stdc++.h>
using namespace std;
char s[1005];
bool palin[1001][1001];
int f[1001];
int n;
int main()
{

    scanf("%s", s + 1); //Đọc dữ liệu vào mảng char, bắt đầu từ 1
    n = strlen(s + 1); //Lấy độ dài của mảng, tính từ 1
    f[1] = 1;
    for (int i = 1; i<=n; i++) {
        palin[i][i] = true;
        int left = i - 1, right = i + 1;
        while (left != 0 && right != n + 1)
        if (s[left] == s[right]) {
            palin[left][right] = true;
            left--;
            right++;
        }
        else break;
        if (s[i] == s[i+1]) {
            palin[i][i+1] = true;
            left = i - 1;
            right = i + 2;
            while (left >= 1 && right <= n) {
                if (s[left] == s[right]) {
                    palin[left][right] = true;
                    left--;
                    right++;
                } else break;
            }

        }
    }

    for (int i = 2; i<=n; i++) {
        f[i] = f[i-1] + 1;
        for (int j = i-1; j>= 1; j--)
            if (palin[j][i] == true)
                f[i] = min(f[i], f[j-1] + 1);
    }
    cout << f[n];
    return 0;
}