# 2472. Maximum Number of Non-overlapping Palindrome Substrings
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/maximum-number-of-non-overlapping-palindrome-substrings/
## 思路
先用区间型I找出所有的是palindrome的substring
然后用另一个dp是一个基本型II的dp ```dp[i]```是```s[0:i]```的maximum number of non-overlapping palindrome
## Code

class Solution {
    public int maxPalindromes(String s, int k) {
        int n = s.length();
        int ans = 0;
        boolean[][] palindrome = new boolean[n][n];
        for(int i=0; i<n; i++) palindrome[i][i] = true;
        for(int len=2; len<n; len++){
            for(int i=0; i+len-1<n; i++){
                int j = i+len-1;
                if(s.charAt(i)==s.charAt(j)){
                    palindrome[i][j] = (j-i==1)?true:palindrome[i+1][j-1];
                }
            }
        }
        int[] dp = new int[n];
        for(int i=0; i<n; i++){
            for(int j=0; j<=i; j++){
                if(palindrome[j][i] && i-j+1>=k){
                    dp[i] = Math.max(dp[i], (j==0?0:dp[j-1])+1);
                }
                else dp[i] = Math.max(dp[i], j==0?0:dp[j-1]);
            }
        }
        return dp[n-1];
    }
}