You are given a string s containing lowercase letters and an integer k. You need to :
First, change some characters of s to other lowercase English letters.
Then divide s into k non-empty disjoint substrings such that each substring is palindrome.
Return the minimal number of characters that you need to change to divide the string.
Example 1:
Input: s = "abc", k = 2
Output: 1
Explanation: You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.
Example 2:
Input: s = "aabbc", k = 3
Output: 0
Explanation: You can split the string into "aa", "bb" and "c", all of them are palindrome.
Example 3:
Input: s = "leetcode", k = 8
Output: 0
Constraints:
1 <= k <= s.length <= 100.
s only contains lowercase English letters.
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        def min_change(s, i, j):
            a = 0
            while i < j:
                if s[i] != s[j]:
                    a+= 1
                
                i += 1
                j -= 1
            return a
        
        cost = [[0 for j in range(len(s) )] for i in range(len(s))]
        n = len(s)
        for l in range(2,n + 1):
            for i in range(n - l + 1):
                j = i + l - 1
                if s[i]!= s[j]:
                    cost[i][j] = cost[i + 1][j - 1] + 1 
                else:
                    cost[i][j] = cost[i + 1][j - 1]
             
        
        
        dp = [[float('inf') for j in range(n)] for i in range(k + 1)]
 
        #print(cost)
        for i in range(n):
            dp[1][i] = cost[0][i]
            for kk in range(2, k+ 1):
                for j in range( i):
                    dp[kk][i] = min(dp[kk][i]  , dp[kk - 1][j]  + cost[j + 1][i])
        
        return dp[-1][-1]
            

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        def min_change(s, i, j):
            a = 0
            while i < j:
                if s[i] != s[j]:
                    a+= 1
                
                i += 1
                j -= 1
            return a
        
        cost = [[0 for j in range(len(s) )] for i in range(len(s))]
        n = len(s)
        for l in range(2,n + 1):
            for i in range(n - l + 1):
                j = i + l - 1
                if s[i]!= s[j]:
                    cost[i][j] = cost[i + 1][j - 1] + 1 
                else:
                    cost[i][j] = cost[i + 1][j - 1]
             
        
        
        dp = [[float('inf') for j in range(n)] for i in range(k + 1)]
 
        #print(cost)
        for i in range(n):
            dp[1][i] = cost[0][i]
            for kk in range(2, k+ 1):
                for j in range( i):
                    dp[kk][i] = min(dp[kk][i]  , dp[kk - 1][j]  + cost[j + 1][i])
        
        return dp[-1][-1]
            
