😕1216 valid palindrome III

https://leetcode.com/problems/valid-palindrome-iii/

首先是要转换思路想到是找多少次delete能让string变成palindrome，然后就类似edit distance了，dp用来记录i - j的字符串需要多少次delete，有点可惜自己没想出来

class Solution {
    public boolean isValidPalindrome(String s, int k) {
        int n = s.length();
        // dp[i][j] is the number of chars deleted to 
        // make subsequence from i to j valid palindrome
        int[][] dp = new int[n][n];
        // len should be the outer loop!!!!!
        for (int len = 1; len < n; len++) {
            for (int i = 0; i + len < n; i++) {
                int j = len + i;
                char ch1 = s.charAt(i);
                char ch2 = s.charAt(j); 
                if (len == 1) {
                    dp[i][j] = ch1 == ch2 ? 0 : 1;
                } else if (ch1 == ch2) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
                }
                
            }
        }
        return dp[0][n - 1] <= k;
    }
}