LeetCode 1216. 验证回文字符串 III（DP）

示例：
输入：s = "abcdeca", k = 2
输出：true
解释：删除字符 “b” 和 “e”。
 
提示：
1 <= s.length <= 1000
s 中只含有小写英文字母
1 <= k <= s.length

class Solution {
public:
    bool isValidPalindrome(string s, int k) {
        int i, j, n = s.size();
    	vector<vector<int>> dp(n,vector<int>(n,0));
        for(i = 0; i < n; ++i)
            dp[i][i] = 1;
    	for(j = 0; j < n; ++j)
    	{
    		for(i = j-1; i >= 0; --i)//区间从小往大，所以逆序
    		{
    			if(s[i] == s[j])
    				dp[i][j] = dp[i+1][j-1]+2;
    			else
    				dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
    		}
    	}
    	return n-dp[0][n-1] <= k;
    }
};

class Solution {
public:
    bool isValidPalindrome(string s, int k) {
        int i, j, n = s.size();
    	vector<vector<int>> dp(n,vector<int>(n,0));
        for(i = 1; i < n; ++i)
            dp[i-1][i] = s[i-1]==s[i] ? 0 : 1;
            //两个字符不一样，需要删除1个才是回文
    	for(j = 0; j < n; ++j)
    	{
    		for(i = j-1; i >= 0; --i)//区间从小往大，所以逆序
    		{
    			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]);
    		}
    	}
    	return dp[0][n-1] <= k;
    }
};