[Python] 2 sub dp
We calculate:\n- number of steps to make any substring (i, j) to be palindrome:\n  dp2(i, j) = dp2(i+1, j-1) + (0 if s[i] == s[j] else 1)\n- minimum number of s
We calculate:\n- number of steps to make any substring `(i, j)` to be palindrome:\n  `dp2(i, j) = dp2(i+1, j-1) + (0 if s[i] == s[j] else 1)`\n- minimum number of steps to get `k` palindrome substrings from `s[0:i]`:\n  `dp(i, k) = min(dp(j, k-1) + dp2(j+1, i) for j in xrange(-1, i))`.\n  \n```python\nclass Solution(object):\n    def palindromePartition(self, s, k):\n        """\n        :type s: str\n        :type k: int\n        :rtype: int\n        """\n        def dp(i, k):\n            if (i, k) in memo: return memo[i, k]\n            if i == -1: memo[i, k] = 0 if k == 0 else float(\'inf\'); return memo[i, k]\n            memo[i, k] = min(dp(j, k-1) + dp2(j+1, i) for j in xrange(-1, i))\n            return memo[i, k]\n        \n        def dp2(i, j):\n            if (i, j) in memo2: return memo2[i, j]\n            if j <= i: memo2[i, j] = 0; return memo2[i, j]\n            if s[i] == s[j]: memo2[i, j] = dp2(i+1, j-1); return memo2[i, j]\n            memo2[i, j] = dp2(i+1, j-1) + 1\n            return memo2[i, j]\n            \n        memo, memo2 = {}, {}\n        return dp(len(s)-1, k)\n```
[]