[Python] O(N*K*N) dp
\nclass Solution:\n    def palindromePartition(self, s: str, K: int) -> int:\n        \n        @cache\n        def palin(l,r):\n            if l==r or l>r:\n  
```\nclass Solution:\n    def palindromePartition(self, s: str, K: int) -> int:\n        \n        @cache\n        def palin(l,r):\n            if l==r or l>r:\n                return 0\n            if s[l]==s[r]:\n                return palin(l+1, r-1)\n            else:\n                return 1+palin(l+1, r-1)\n         \n        n=len(s)\n        inf=float(\'inf\')\n        dp=[[inf for _ in range(K+1)] for _ in range(n)]\n        \n        \n        for i in range(n):\n            dp[i][1]=palin(0,i)\n        \n        print(dp)\n        \n            \n        for i in range(n):\n            for k in range(2, K+1):\n                if i+1<k:continue\n                for j in range(i):\n                    dp[i][k]=min(dp[i][k], dp[j][k-1]+palin(j+1, i))\n        \n        \n        return dp[-1][K]\n                \n            \n            \n        \n```
[]