题目：原题链接（困难）

标签：动态规划、字符串

解法	时间复杂度	空间复杂度	执行用时
Ans 1 (Python)	$O(N^2)$	$O(N^2)$	324ms (53.85%)
Ans 2 (Python)
Ans 3 (Python)

解法一：

class Solution:def isValidPalindrome(self, s: str, k: int) -> bool:size = len(s)# dp[i][j] = 令字符串[i,j]变为回文串需要删除的字符数dp = [[float("inf")] * size for _ in range(size)]for i in range(size):dp[i][i] = 0for length in range(2, size + 1):for i in range(size - length + 1):j = i + length - 1if s[i] == s[j]:if length == 2:dp[i][j] = 0else:dp[i][j] = dp[i + 1][j - 1]else:dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1return dp[0][-1] <= k