# 1278. Palindrome Partitioning III
###### tags: `Leetcode` `Dynamic Programming` `Hard`
Link: https://leetcode.com/problems/palindrome-partitioning-iii/
## 思路
要注意找palindrome substring的写法
两层回圈一层是len 一层是i(0:n) 如果写成一层是i(0:n) 一层是j(0:n)就会错

如果是求最小值 一定要记得初始化dp的时候给所有位置赋最大值

## Code

class Solution {
    public int palindromePartition(String s, int k) {
        int n = s.length();
        int[][] cnt = new int[n][n];
        //minimum number characters need to change for every substring
        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))
                    cnt[i][j] = cnt[i+1][j-1];
                else
                    cnt[i][j] = cnt[i+1][j-1]+1;
            }
        }
        StringBuilder str = new StringBuilder(s);
        str.insert(0, '#');
        int[][] dp = new int[n+1][k+1];
        for(int i=1; i<=n; i++) dp[i][0]=Integer.MAX_VALUE/2;
        // dp[i][k]: minimum number of characters need to change if we split s[1:i] into k groups
        for(int i=1; i<=n; i++){
            for(int tempk=1; tempk<=Math.min(k,i); tempk++){
                dp[i][tempk] = Integer.MAX_VALUE;
                for(int j=tempk; j<=i; j++){
                    dp[i][tempk] = Math.min(dp[j-1][tempk-1]+cnt[j-1][i-1], dp[i][tempk]);
                }
            }
        }
        
        return dp[n][k];
    }
}