1332. Remove Palindromic Subsequences

這題難怪到讚多了,

有幾個點我看太快沒有注意到, 第一 他可以刪掉子序列

第二, 整個字串只有a b,

所以最大就是兩步, 第一步是刪掉所有的a, 第二步是刪掉所有的b

最少是 剛好這個字串就是迴文

我原本以為是跟131. Palindrome Partitioning一樣的題目魔改

害我還寫得很完整, 傻眼

class Solution {
public:
   
    int removePalindromeSub(string s) {
        int n = s.size();
        if(s.size() == 0) return 0;
        string re = s;
        reverse(re.begin(), re.end());
        if(s == re) return 1;
        return 2;
    }
};

都寫了也放一下, 說不定哪天就有類似的題目出現

class Solution {
public:
    void dfs(string &s, vector<vector<bool>>&dp, int start, vector<string> cur, int &res){
        if(start == s.size()){
            res = min(res, (int)cur.size());
            return;
        }
        for(int i= start; i < s.size();i++){
            if(!dp[start][i]) continue;
            cur.push_back(s.substr(start, i - start +  1));
            dfs(s, dp, i + 1, cur, res);
            cur.pop_back();
        }
        return;
    }
    int removePalindromeSub(string s) {
        int n = s.size();
        if(s.size() == 0) return 0;
        vector<vector<bool>> dp(n, vector<bool>(n, false));
        for(int i = 0; i < n;i++){
            for(int j = 0; j <=i;j++){
                if(i == j) dp[j][i] = true;
                else if (j + 1 == i) dp[j][i] = s[i] == s[j];
                else{
                    dp[j][i] = dp[j + 1][i - 1] && s[i] == s[j];
                }
            }
        }
        int res= INT_MAX;
        vector<string> cur;
        dfs(s, dp, 0, cur, res);
        return res;
    }
};