<p>You are given a string <code>s</code> containing lowercase letters and an integer <code>k</code>. You need to :</p>

<ul>
	<li>First, change some characters of <code>s</code> to other lowercase English letters.</li>
	<li>Then divide <code>s</code> into <code>k</code> non-empty disjoint substrings such that each substring is a palindrome.</li>
</ul>

<p>Return <em>the minimal number of characters that you need to change to divide the string</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abc&quot;, k = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong>&nbsp;You can split the string into &quot;ab&quot; and &quot;c&quot;, and change 1 character in &quot;ab&quot; to make it palindrome.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;aabbc&quot;, k = 3
<strong>Output:</strong> 0
<strong>Explanation:</strong>&nbsp;You can split the string into &quot;aa&quot;, &quot;bb&quot; and &quot;c&quot;, all of them are palindrome.</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;leetcode&quot;, k = 8
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= s.length &lt;= 100</code>.</li>
	<li><code>s</code> only contains lowercase English letters.</li>
</ul>

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        #先假設
        #dp[i][k] = 在目前為止切成 k 個 non-empty disjoint substrings 在i 結尾的地方 最少要換多少個 character
        # x x x 
        # ^   ^
        # 代表要 <= 才會交錯 這樣子寫可以同時處理奇數和偶數
        # def help(l,r):
        #     tmp = 0
        #     while l >= 0 and r < n and l<=r:
        #         if s[l]!=s[r]:
        #             tmp+=1
        #         l-=1
        #         r+=1
        #     return tmp
                
        # n = len(s)
        # memo = {}
        # # j i
        # def dfs(i,k):
        #     if k==1:
        #         return help(0,i)
        #     if (i,k) in memo:
        #         return memo[(i,k)]
        #     tmp = inf
        #     for j in range(k-2,i):
        #         tmp = min(tmp,dfs(j-1,k-1)+help(j,i))
            
        #     memo[(i,k)] = tmp 
        #     return tmp
        
        # ret  = dfs(n-1,k)  
        # print(memo)     
        # return ret
                # 用來計算把子字串 s[l:r+1] 變成回文所需的最少變動次數
        def help(l, r):
            tmp = 0
            while l < r:  # 這裡不應該包含 l <= r，因為當 l == r 時，單個字符不需要變動
                if s[l] != s[r]:
                    tmp += 1
                l += 1
                r -= 1
            return tmp
        
        n = len(s)
        memo = {}
        
        # dp 函數：找到把前 i 個字符分割成 k 個子字串的最小修改次數
        def dfs(i, k):
            if k == 1:  # 當 k == 1 時，計算 s[0:i] 這段變成回文的最少修改次數
                return help(0, i)
            if (i, k) in memo:  # 查找是否已經計算過這個狀態
                return memo[(i, k)]
            tmp = float('inf')
            # 確保每一個子區間都不為空，因此 j 的範圍應該從 k-2 到 i-1
            for j in range(k-2, i):
                tmp = min(tmp, dfs(j, k-1) + help(j+1, i))  # 將 s[j+1:i] 當成新的一段子字串
            memo[(i, k)] = tmp  # 儲存當前狀態的結果
            return tmp if tmp!=inf else 0
        
        return dfs(n-1, k)
16900