python easy dp solution
Simple Knapsack problem, dp(i,k)=dp(j,k-1)+num_change(s[j+1....i]) for j=k-1.\n```\nclass Solution(object):\n    def palindromePartition(self, s, k):\n        d
Simple Knapsack problem, dp(i,k)=dp(j,k-1)+num_change(s[j+1....i]) for j<i and j+1>=k-1.\n```\nclass Solution(object):\n    def palindromePartition(self, s, k):\n        def num_change(w):#number need to change to become palindrome\n            l,r=0,len(w)-1\n            count=0\n            while l<r:\n                if w[l]!=w[r]:\n                    count+=1\n                l+=1\n                r-=1\n            return count\n        \n        def dp(i,k):\n            if (i,k) not in memo:\n                if k==1:\n                    memo[i,k]=num_change(s[:i+1])\n                else:\n                    memo[i,k]=min(dp(j,k-1)+num_change(s[j+1:i+1]) for j in range(k-2,i))\n            return memo[i,k]\n        memo={}    \n        n=len(s)\n        return dp(n-1,k)
[]