+4

Quy hoạch động 7.4: Palindromes và Các bài toán QHĐ liên quan

I. Những bài toán cơ sở

Trong Lập trình thi đấu, xâu palindrome (xâu đối xứng) là một loại xâu kí tự đặc biệt. Đó là những xâu mà viết xuôi hay viết ngược đều giống nhau, chẳng hạn như ABBA hay TOEICCIEOT,...Nhờ tính chất đặc biệt này, người ta phát triển ra rất nhiều bài toán liên quan tới xâu palindrome, không chỉ ở trong xâu kí tự mà còn có thể phát triển sang các bài tập trên dãy số, nhưng chủ yếu là dạng bài tập Quy hoạch động.

Trong chuyên đề này, tôi sẽ giới thiệu tới các bạn một số bài tập như vậy. Nhưng trước hết ta hãy cùng đến với những bài toán cơ sở trước đã.

1. Kiểm tra xâu palindrome

Đề bài

Cho một xâu kí tự ss độ dài nn. Kiểm tra xem xâu đó có phải xâu palindrome không?

Input:

  • Dòng đầu tiên chứa số nguyên dương TT - số lượng test cases.
  • Chứa duy nhất xâu kí tự ss độ dài nn.

Ràng buộc:

  • 1T1001 \le T \le 100.
  • 1n1061 \le n \le 10^6.

Output:

  • In ra Yes nếu xâu ss đối xứng, ngược lại in ra No. Kết quả của mỗi test case in ra trên một dòng.

Sample Input:

2
ABA
TOEIC

Sample Output:

Yes
No

Ý tưởng

Đây là một bài tập đơn giản mà bạn nào cũng phải làm qua khi mới bắt đầu học về xâu kí tự trong lập trình. Mặc dù vậy, tôi vẫn nói tới bài toán này vì ở những bài tập tiếp theo, chúng ta sẽ dùng nhiều tới việc kiểm tra tính đối xứng của một xâu.

Giả sử ta đánh số thứ tự của các kí tự trong xâu từ 00 và kết thúc tại n1n - 1. Một xâu là đối xứng khi và chỉ khi nó thỏa mãn điều kiện:

si=snii;i:0in12s_i = s_{n - i - i}; \forall i: 0 \le i \le \left\lfloor{\frac{n - 1}{2}} \right\rfloor

Vậy ta kiểm tra bằng một vòng lặp, độ phức tạp O(n)O(n).

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

bool is_palin(string &s)
{
    int n = s.size();
    for (int i = 0; i <= (n - 1) / 2; ++i)
        if (s[i] != s[n - i - i])
            return false;

    return true;
}

main()
{
    int t;
    cin >> t;

    while (t--)
    {
        string s;
        cin >> s;

        if (is_palin(s))
            cout << "Yes" << endl;
        else 
            cout << "No" << endl;
    }
}

Ngôn ngữ Python:

def is_palin(s):
    n = len(s)
    for i in range((n - 1) / 2 + 1):
        if s[i] != s[n - i - 1]:
            return False

    return True


if __name__ == '__main__':
    t = int(input())

    for _ in range(t):
        s = input()

        if is_palin(s):
            print(Yes)
        else:
            print(No)

2. Xâu con palindrome dài nhất

Đề bài

Cho một xâu ss độ dài nn. Hãy xác định độ dài xâu con đối xứng dài nhất trong s?s?

Input:

  • Một dòng duy nhất chứa xâu kí tự ss độ dài nn.

Ràng buộc:

  • 1n10001 \le n \le 1000.

Output:

  • In ra độ dài của xâu con đối xứng dài nhất tìm được trong ss.

Sample Input:

abcddcbfgh

Sample Output:

6

Ý tưởng

Cách làm duyệt mọi xâu con trong xâu ban đầu rồi kiểm tra tính đối xứng của từng xâu, chắc chắn không thể thỏa mãn yếu tố thời gian thực thi nên ta sẽ không bàn tới nữa.

Bài toán này có nhiều cách tiếp cận với những độ phức tạp khác nhau, nhưng ở đây tôi sẽ hướng dẫn các bạn hướng tiếp cận đơn giản nhất với độ phức tạp là O(n2)O(n^2) là quy hoạch động.

Gọi palin[i][j]\text{palin}[i][j] là mảng đánh dấu xâu con si,js_{i, j} có phải xâu đối xứng hay không: palin[i][j]=1\text{palin}[i][j] = 1 nếu xâu con si,js_{i, j} đối xứng, ngược lại thì palin[i][j]=0\text{palin}[i][j] = 0.

Xét cặp kí tự si,sj,s_i, s_j, ta xây dựng công thức truy hồi để tính palin[i][j]\text{palin}[i][j] như sau:

  • Nếu si=sj,s_i = s_j, thì xâu con si...js_{i...j} có đối xứng hay không sẽ phụ thuộc vào xâu con si+1,j1s_{i + 1, j - 1}. Thiết lập công thức:

    palin[i][j]=palin[i+1][j1]\text{palin}[i][j] = \text{palin}[i + 1][j - 1]

  • Nếu sisj,s_i \ne s_j, hiển nhiên xâu con si...js_{i...j} không đối xứng, ta có công thức:

    palin[i][j]=0\text{palin}[i][j] = 0

Về cơ sở quy hoạch động, dễ dàng nhận ra:

  • Xâu con có 11 kí tự luôn luôn là đối xứng: palin[i][j]=1\text{palin}[i][j] = 1.
  • Xâu con có 22 kí tự đối xứng hay không tùy vào hai kí tự đó: palin[i][i+1]=1\text{palin}[i][i + 1] = 1 nếu si=si+1s_i = s_{i + 1}.

Cuối cùng kết quả sẽ là max(ji+1)\text{max}(j - i + 1) với các căp (i,j)(i, j) thỏa mãn palin[i][j]=1\text{palin}[i][j] = 1.

Độ phức tạp của cách này là O(n2)O(n^2).

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

main()
{
    string s;
    cin >> s;

    s = '  ' + s;
    int n = s.size() - 1;
    vector < vector < int > > palin(n + 1, vector < int >(n + 1, 0));

    // Cơ sở quy hoạch động.
    for (int i = 1; i <= n; ++i)
    {
        palin[i][i] = 1;
        
        if (i < n)
            palin[i][i + 1] = (a[i] == a[i + 1]);
    }

    // Tính bảng phương án.
    for (int j = n; j >= 3; --j)
        for (int i = 1; i <= j - 2; ++i)
            palin[i][j] = (palin[i + 1][j - 1] & (s[i] == s[j]));

    // Tìm kết quả cuối cùng.
    int res = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j)
            if (palin[i][j])
                res = max(res, j - i + 1);

    cout << res;
}

Ngôn ngữ Python:

if __name__ == '__main__':
    s = ' ' + input()
    n = len(s) - 1

    # Cơ sở quy hoạch động.
    palin = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        palin[i][i] = 1

        if i < n:
            palin[i][i + 1] = 1 if s[i] = s[i + 1] else 0

    # Tính bảng phương án.
    for j in range(n, 2, -1):
        for i in range(1, j - 1):
            palin[i][j] = (palin[i + 1][j - 1] and s[i] == s[j])

    # Tìm kết quả cuối cùng.
    res = 0
    for i in range(1, n + 1):
        for j in range(i, n + 1):
            if palin[i][j]:
                res = max(res, j - i + 1)
    
    print(res)

II. Một số bài toán khác liên quan

1. Chia xâu thành các Palindromes

Đề bài

Cho một xâu ss độ dài nn. Hãy tìm cách chia nó thành một số ít nhất các xâu con liên tiếp, sao cho mỗi xâu con đều là một palindrome?

Input:

  • Một dòng duy nhất chứa xâu kí tự ss độ dài nn.

Ràng buộc:

  • 1n10001 \le n \le 1000.

Output:

  • Một số nguyên duy nhất là số lượng đoạn tối thiểu chia được.

Sample Input:

abacc

Sample Output:

2

Giải thích:

Chia xâu ban đầu thành 22 xâu con đối xứng là abacc.

Ý tưởng

Coi rằng xâu ss ban đầu được đánh số kí tự từ vị trí 11.

Vẫn sử dụng quy hoạch động, ta sẽ gọi dp[i]dp[i] là số lượng xâu con đối xứng tối thiểu chia được từ xâu s1...is_{1...i}. Công thức được thiết lập khá đơn giản: Nếu như đoạn sj+1...is_{j + 1...i} là một xâu đối xứng thì dp[i]dp[i] có thể gán bằng dp[j]+1dp[j] + 1. Mà ta mong muốn kết quả nhỏ nhất, vì thế:

dp[i]=min(dp[j]+1)dp[i] = \text{min}\big(dp[j] + 1\big)

<center>

với xâu con sj+1...is_{j + 1...i} là đối xứng

</center>

Đến đây, công việc còn lại là kiểm tra một xâu con sj...is_{j...i} có phải đối xứng hay không. Nếu như sử dụng lại vòng lặp, thì độ phức tạp thuật toán sẽ là O(n3),O(n^3), không thể đáp ứng giới hạn n1000n \le 1000. Thay vào đó, ta sẽ khởi tạo trước một mảng palin[i][j]\text{palin}[i][j] giống như bài toán trước để xác định đoạn [i...j][i...j] có phải là một xâu đối xứng hay không bằng hai vòng lặp. Sau đó, giải thuật sẽ trở thành:

dp[i]=min(dp[j]+1);neˆˊf[j+1][i]=1dp[i] = \text{min}\big(dp[j] + 1\big); \text{nếu } f[j + 1][i] = 1

Cơ sở quy hoạch động khởi tạo dp[i]=;i:1indp[i] = \infty; \forall i: 1 \le i \le n. Riêng dp[1]=1dp[1] = 1.

Độ phức tạp giải thuật lúc này giảm xuống O(n2)O(n^2).

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>

using namespace std;

vector < vector < int > > data_preparation(string &s, int n)
{
    vector < vector < int > > palin(n + 1, vector < int >(n + 1, 0));
    for (int i = 1; i <= n; ++i)
    {
        palin[i][i] = 1;
        
        if (i < n)
            palin[i][i + 1] = (s[i] == s[i + 1]);
    }

    for (int j = n; j >= 3; --j)
        for (int i = 1; i <= j - 2; ++i)
            palin[i][j] = (palin[i + 1][j - 1] & (s[i] == s[j]));

    return palin;
}

void solution(int n, vector < vector < int > > &palin)
{
    vector < int > dp(n + 1, 1001);
    dp[1] = 1;

    for (int i = 2; i <= n; ++i)
        for (int j = i - 1; j >= 0; --j)
            if (palin[j + 1][i])
                dp[i] = min(dp[i], dp[j] + 1);

    cout << dp[n];
}

main()
{
    string s;
    cin >> s;

    s = ' ' + s;
    int n = s.size() - 1;
    vector < vector < int > > palin = data_preparation(s, n);

    solution(n, palin);
}

Ngôn ngữ Python:

def data_preparation(s, n):
    palin = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        palin[i][i] = 1

        if i < n:
            palin[i][i + 1] = 1 if s[i] = s[i + 1] else 0

    for j in range(n, 2, -1):
        for i in range(1, j - 1):
            palin[i][j] = (palin[i + 1][j - 1] and s[i] == s[j])

    return palin


def solution(s, n, palin):
    dp = [1001] * (n + 1)
    dp[1] = 1

    for i in range(2, n + 1):
        for j in range(0, i):
            if palin[j + 1][i]:
                dp[i] = min(dp[i], dp[j] + 1)

    print(dp[n])


if __name__ == '__main__':
    s = ' ' + input()    
    
    n = len(s) - 1
    palin = data_preparation(s, n)

    solution(n, palin)

2. Đếm số xâu con là Palindrome

Đề bài

Cho một xâu kí tự ss độ dài nn. Ở đây, ta định nghĩa "xâu con" của ss là một hoặc một số kí tự không cần liên tiếp nhau của s,s, giữ nguyên thứ tự của chúng trong xâu ban đầu.

Hãy đếm số lượng "xâu con" là đối xứng của s?s?

Input:

  • Một dòng duy nhất chứa xâu kí tự ss độ dài nn.

Ràng buộc:

  • 1n10001 \le n \le 1000.

Output:

  • In ra một số nguyên là số lượng xâu con đối xứng của ss. Do kết quả có thể rất lớn, chỉ cần in ra phần dư của kết quả sau khi chia cho 109+710^9 + 7.

Sample Input:

IOICAMP

Sample Output:

9

Giải thích:

Các xâu con đối xứng là: I, O, I, C, A, M, P, II, IOI.

Ý tưởng

Ý tưởng của bài tập này là sử dụng quy hoạch động. Ta nhận ra bài toán có bản chất đệ quy, bởi nếu coi dp[i][j]dp[i][j] là số xâu con đối xứng trong đoạn vị trí [i,j][i, j] của s,s, thì ta xây dựng được công thức truy hồi như sau:

  • Nếu sisj,s_i \ne s_j, thì số lượng xâu con đối xứng của đoạn [i,j][i, j] chỉ phụ thuộc vào số lượng xâu con đối xứng của đoạn [i+1,j][i + 1, j][i,j1][i, j - 1]. Ngoài ra, ta lại phải trừ bớt đi số lượng xâu con bị trùng lặp hai lần tính trong đoạn [i+1,j1][i + 1, j - 1]. Tức là:

    dp[i][j]=dp[i+1][j]+dp[i][j1]dp[i+1][j1]dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]

  • Nếu si=sj,s_i = s_j, thì số lượng xâu con đối xứng của của đoạn [i,j][i, j] sẽ có thêm một xâu là sisj,s_is_j, đồng thời cũng cộng với số lượng xâu con đối xứng ở giữa gộp từ hai đoạn [i+1,j],[i,j1][i + 1, j], [i, j - 1] và trừ bớt đi số lượng xâu con bị trùng lặp hai lần tính trong đoạn [i+1,j1][i + 1, j - 1]. Tuy nhiên, cần lưu ý rằng, bây giờ mỗi xâu con đối xứng trong đoạn [i+1,j1][i + 1, j - 1] lại có thể tạo thành thêm một xâu con đối xứng nữa bằng cách ghép sis_isjs_j vào hai đầu xâu đó. Vì thế, ta có công thức:

    dp[i][j]=dp[i+1][j]+dp[i][j1]dp[i+1][j1]+dp[i+1][j1]+1dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + dp[i + 1][j - 1] + 1

    =dp[i+1][j]+dp[i][j1]+1= dp[i + 1][j] + dp[i][j - 1] + 1

Cơ sở quy hoạch động của bài toán là dp[i][i]=1dp[i][i] = 1 - mọi đoạn độ dài 11 đều chỉ có 11 xâu con đối xứng. Kết quả cuối cùng dĩ nhiên là dp[1][n]dp[1][n].

Bằng hai vòng lặp, ta có thể tính được bảng phương án trong O(n2)O(n^2). Lưu ý cần kết hợp với đồng dư để đưa ra được kết quả đề bài yêu cầu.

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int mod = 1e9 + 7;

void solution(string &s, int n)
{
    vector < vector < int > > dp(n + 1, vector < int >(n + 1));
    for (int i = 1; i <= n; ++i)
        dp[i][i] = 1;

    for (int l = 2; l <= n; ++l)
        for (int i = 1; i <= n - l + 1; ++i)
        {
            int j = i + l - 1;

            dp[i][j] = (dp[i + 1][j] + dp[i][j - 1]) % mod;

            if (s[i] == s[j])
                (dp[i][j] += 1) %= mod;
            else 
                dp[i][j] = (dp[i][j] - dp[i + 1][j - 1] + mod) % mod;
        }

    cout << dp[1][n];
}

main()
{
    string s;
    cin >> s;

    s = ' ' + s;
    int n = s.size() - 1;

    solution(s, n);
}

Ngôn ngữ Python:

def solution(s, n):
    mod = 10**9 + 7
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dp[i][i] = 1

    for l in range(2, n + 1):
        for i in range(1, n - l + 2):
            j = i + l - 1

            dp[i][j] = (dp[i + 1][j] + dp[i][j - 1]) % mod

            if s[i] == s[j]:
                (dp[i][j] += 1) %= mod
            else:
                (dp[i][j] -= dp[i + 1][j - 1]) %= mod

    print(dp[1][n])


if __name__ == '__main__':
    s = ' ' + input()
    n = len(s) - 1

    solution(s, n)

3. Xóa xâu con

Đề bài

Cho xâu kí tự ss chỉ gồm các chữ cái latin in thường. Ở mỗi bước, bạn được phép chọn ra một xâu con liên tiếp của ss và xóa nó đi, với điều kiện xâu con đó phải là xâu đối xứng.

Hãy đếm số bước ít nhất để xóa toàn bộ xâu s?s?

Input:

  • Dòng đầu tiên chứa số nguyên dương T – số lượng test cases.
  • TT dòng tiếp theo, mỗi dòng chứa một xâu kí tự ss.

Ràng buộc:

  • 1T51 \le T \le 5.
  • 1s300;1 \le |s| \le 300; với s|s| là độ dài xâu ss.

Output:

  • In ra số lượng kí tự tối thiểu cần thêm vào.

Sample Input:

2
teen
aadcbcab

Sample Output:

3
4

Ý tưởng

Gọi dp[i][j]dp[i][j] là số thao tác tối thiểu để xóa đoạn [i,j][i, j] của xâu ss.

Xét đoạn [i,j],[i, j], ta có:

  • Nếu như si=sj,s_i = s_j, thì ta xóa hết đoạn [i+1,j1],[i + 1, j - 1], đồng thời ở thao tác xóa cuối cùng, ta gộp luôn hai kí tự si,sjs_i, s_j vào hai đầu của xâu đối xứng cuối cùng và xóa chung. Vì thế:

    dp[i][j]=dp[i+1][j1]dp[i][j] = dp[i + 1][j - 1]

  • Còn nếu sisj,s_i \ne s_j, thì có thể tồn tại ba cách xóa:

    • Xóa đoạn [i,j1][i, j - 1] rồi mới xóa sjs_j.
    • Xóa đoạn [i+1,j][i + 1, j] rồi mới xóa sis_i.
    • Xóa một đoạn đối xứng liên tiếp [i,k][i, k] rồi xóa đoạn [k+1,j][k + 1, j].

    Ta rút ra công thức:

    dp[i][j]=min(dp[i+1][j]+1,dp[i][j1]+1,dp[i][k]+dp[k+1][j]);k:ik<jdp[i][j] = \text{min}\big(dp[i + 1][j] + 1, dp[i][j - 1] + 1, dp[i][k] + dp[k + 1][j]\big); \forall k: i \le k < j

Về cơ sở quy hoạch động, ta có dp[i][i]=1dp[i][i] = 1 - cần một thao tác để xóa các xâu con độ dài 1,1,dp[i][i+1]=1dp[i][i + 1] = 1 hoặc 00 tùy thuộc vào sis_i có bằng si+1s_{i + 1} hay không. Kết quả cuối cùng tất nhiên là dp[1][n]dp[1][n].

Độ phức tạp: O(n3)O(n^3).

Cài đặt

Ngôn ngữ C++:

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int INFTY = 1e9 + 7;

void solution(string &s)
{
    s = ' ' + s;
    int n = s.size() - 1;
    vector < vector < int > > dp(n + 1, vector < int >(n + 1, INFTY));

    for (int i = 1; i <= n; ++i)
    {
        dp[i][i] = 1;

        if (i < n)
            dp[i][i + 1] = (s[i] == s[i + 1]) ? 1 : 2;
    }

    for (int len = 3; len <= n; ++len)
    {
        for (int i = 1; i <= n - len + 1; ++i)
        {
            int j = i + len - 1;

            if (s[i] == s[j])
                dp[i][j] = dp[i + 1][j - 1];
            else
                dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1]);

            for (int k = i; k < j; ++k)
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
        }
    }

    cout << dp[1][n] << endl;
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int ntest;
    cin >> ntest;

    while (ntest--)
    {
        string s;
        cin >> s;

        solution(s);
    }

    return 0;
}

Ngôn ngữ Python:

INFTY = 10**9 + 7


def solution(s):
    n = len(s) - 1
    dp = [[INFTY] * (n + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        dp[i][i] = 1

        if i < n:
            dp[i][i + 1] = 1 if s[i] == s[i + 1] else 2

    for l in range(3, n + 1):
        for i in range(1, n - l + 2):
            j = i + l - 1

            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1])

            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])

    print(dp[1][n])


if __name__ == '__main__':
    t = int(input())

    for _ in range(t):
        s = ' ' + input()

        solution(s)

III. Tài liệu tham khảo


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.