1216. Valid Palindrome III

dp O(n²) time O(n²) space
区间型dp
算一下s[0:n-1]的最长回文子序列长度f[0][n - 1]
n - f[0][n - 1]是不在最长回文子序列里的即要从原字符串删除的字符个数
最后要判断n - f[0][n - 1]是否不超过k

class Solution {
public:
    bool isValidPalindrome(string s, int k) {
        int n = s.length();
        vector<vector<int>> f(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            f[i][i] = 1;
        }
        for (int i = 0; i < n - 1; ++i) {
            f[i][i + 1] = 1 + (s[i] == s[i + 1]);
        }
        for (int len = 2; len < n; ++len) {
            for (int i = 0, j = i + len; j < n; ++i, ++j) {
                if (s[i] == s[j]) {
                    f[i][j] = f[i + 1][j - 1] + 2;
                } else {
                    f[i][j] = max(f[i][j - 1], f[i + 1][j]);
                }
            }
        }
        return n - f[0][n - 1] <= k;
    }
};