Tóm tắt đề bài

Cho một xâu ~s~ chỉ gồm các ký tự in thường. Hãy loại bỏ ít ký tự nhất, mà sau khi loại bỏ xâu ~s~ là xâu đối xứng.

Giới hạn: độ dài xâu ~s \le 2000~.

Lời giải

• Ta sẽ định nghĩa lại bài toán: Ta cần tìm xâu con dài nhất (có thể không cần liên tiếp) của xâu ~s~, mà xâu đó là xâu đối xứng.
• Bài toán này có thể xử lý bằng quy hoạch động.
• Gọi ~dp[i][j]~ là độ dài xâu con dài nhất trong xâu ~s[i] \rightarrow s[j]~ mà xâu đó là xâu đối xứng
• Ta có công thức truy hồi:
  • ~dp[i][i] = 1~ với mọi ~1 \le i \le n~.
  • ~dp[i][i + 1] = 2~ với mọi ~1 \le i < n~ và ~s_i = s_{i + 1}~.
  • ~dp[i][j] = dp[i + 1][j - 1] + 2~ với ~s_i = s_j~.
  • ~dp[i][j] = max (dp[i + 1][j], dp[i][j - 1])~ với ~s_i \neq s_j~.
• Kết quả sẽ là ~n - dp[1][n]~ do ~dp[1][n]~ là độ dài xâu con dài nhất trong ~s~ mà xâu đó là xâu đối xứng.

Độ phức tạp: ~O~ ~(n^2)~