方法思路

这道题目可以使用区间动态规划来解决。我们需要计算最少需要多少次操作可以将整个字符串删光，每次操作可以删除一个回文子串。

关键点：

1. 定义状态：dp[i][j]表示将区间[i:j]全部删除所需的最少操作次数
2. 状态转移有两种情况：
   • 如果s[i]==s[j]且区间[i+1:j-1]是回文或为空，则可以一次性删除整个区间
   • 如果s[i]==s[j]但区间[i+1:j-1]不是回文，则可以先删除中间部分，再一次性删除两端
   • 否则，尝试在任意位置k将区间分为两部分，取最小操作次数
3. 状态初始化：
   • dp[i][i]=1，单个字符需要1次操作
   • 对于长度为2的子串，如果两个字符相同，dp[i][i+1]=1，否则dp[i][i+1]=2

代码实现

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        
        for (int i = 0; i < t; i++) {
            String s = br.readLine();
            bw.write(minOperations(s) + "\n");
        }
        
        br.close();
        bw.flush();
        bw.close();
    }
    
    public static int minOperations(String s) {
        int n = s.length();
        char[] chars = s.toCharArray(); // 转换为字符数组，提高访问速度
        
        // 判断区间[i,j]是否为回文串
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            isPalindrome[i][i] = true; // 单个字符是回文串
        }
        
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                if (chars[i] == chars[j]) {
                    if (len == 2 || isPalindrome[i+1][j-1]) {
                        isPalindrome[i][j] = true;
                    }
                }
            }
        }
        
        // dp[i][j]表示将区间[i,j]全部删除所需的最少操作次数
        int[][] dp = new int[n][n];
        
        // 初始化：单个字符需要1次操作
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        
        // 初始化：长度为2的子串
        for (int i = 0; i < n - 1; i++) {
            if (chars[i] == chars[i + 1]) {
                dp[i][i + 1] = 1; // 两个相同字符可以一次删除
            } else {
                dp[i][i + 1] = 2; // 两个不同字符需要两次删除
            }
        }
        
        // 按照区间长度从小到大进行动态规划
        for (int len = 3; len <= n; len++) {
            for (int i = 0; i <= n - len; i++) {
                int j = i + len - 1;
                
                // 如果区间[i,j]是回文串，可以一次删除
                if (isPalindrome[i][j]) {
                    dp[i][j] = 1;
                    continue;
                }
                
                // 初始化为分割后的最小值
                dp[i][j] = Integer.MAX_VALUE;
                
                // 如果s[i]==s[j]，可以先删除中间部分，再一次性删除两端
                if (chars[i] == chars[j]) {
                    dp[i][j] = dp[i+1][j-1];
                }
                
                // 尝试在任意位置k将区间分为两部分
                for (int k = i; k < j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j]);
                }
            }
        }
        
        return dp[0][n-1];
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

int minOperations(const string& s) {
    int n = s.length();
    
    // 判断区间[i,j]是否为回文串
    vector<vector<bool>> isPalindrome(n, vector<bool>(n, false));
    for (int i = 0; i < n; i++) {
        isPalindrome[i][i] = true; // 单个字符是回文串
    }
    
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s[i] == s[j]) {
                if (len == 2 || isPalindrome[i+1][j-1]) {
                    isPalindrome[i][j] = true;
                }
            }
        }
    }
    
    // dp[i][j]表示将区间[i,j]全部删除所需的最少操作次数
    vector<vector<int>> dp(n, vector<int>(n));
    
    // 初始化：单个字符需要1次操作
    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }
    
    // 初始化：长度为2的子串
    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = 1; // 两个相同字符可以一次删除
        } else {
            dp[i][i + 1] = 2; // 两个不同字符需要两次删除
        }
    }
    
    // 按照区间长度从小到大进行动态规划
    for (int len = 3; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            
            // 初始化为最大值
            dp[i][j] = INT_MAX;
            
            // 如果区间[i,j]是回文串，可以一次删除
            if (isPalindrome[i][j]) {
                dp[i][j] = 1;
                continue;
            }
            
            // 如果s[i]==s[j]，可以先删除中间部分，再一次性删除两端
            if (s[i] == s[j]) {
                dp[i][j] = min(dp[i][j], dp[i+1][j-1]);
            }
            
            // 尝试在任意位置k将区间分为两部分
            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
            }
        }
    }
    
    return dp[0][n-1];
}

int main() {
    int t;
    cin >> t;
    
    for (int i = 0; i < t; i++) {
        string s;
        cin >> s;
        cout << minOperations(s) << endl;
    }
    
    return 0;
}