Clean and consice code | Recursion + Memoization
Intuition\n Describe your first thoughts on how to solve this problem. \nSince constraints are very small we can try out all the possibilities and pick the best
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSince constraints are very small we can try out all the possibilities and pick the best one.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThere will be case when we encounter overlapping subproblems so dp is the goto approach for this.\n\nWe need **K** segments of string so we require **K-1** cuts.\n\n# Complexity\n- Time complexity: O(n\\*n*k)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n*k)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int dp[105][105];\n    int cost(int left,int right,string& s){\n        int ct = 0;\n        while(left < right){\n            ct += (s[left++] != s[right--]);\n        }\n        return ct;\n    }\n    int solve(int ind,string& s,int cut){\n        if(ind == s.size()){\n            return cut < 0 ? 0 :1e9;\n        }\n        if(cut == 0){\n            return cost(ind,s.size() - 1,s);\n        }\n        if(dp[ind][cut] != -1){\n            return dp[ind][cut];\n        }\n        int ans = 1e9;\n        for(int i=ind;i<s.size();i++){\n            int tmp = cost(ind,i,s) + solve(i+1,s,cut-1);\n            ans = min(tmp,ans);\n        }\n        return dp[ind][cut] = ans;\n    }\n    int palindromePartition(string s, int k) {\n        k--;\n        memset(dp,-1,sizeof(dp));\n        return solve(0,s,k);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'Memoization', 'C++']