Recursion + Memoization | C++ | Cut / NotCut Method
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int check(string s)\n    {\n        int n = s.size(), ans = 0;\n        for(int i = 0; i < (n / 2); i++)\n        {\n            if(s[i] != s[n - i - 1])\n                ans++;\n        }\n        return ans;\n    }\n    int dp[101][101];\n    int rec(string s, int i, int prev, int k)\n    {\n        if(k == 1)\n        {\n            if(i == s.size())   return 1e9;\n            return check(s.substr(i));\n        }\n        if(i == s.size())   return 1e9;\n        if(dp[prev][k] != -1)   return dp[prev][k];\n        int cut = check(s.substr(prev, (i - prev + 1))) + rec(s, i + 1, i + 1, k - 1);\n        int notCut = rec(s, i + 1, prev, k);\n        return dp[prev][k] = min(cut, notCut);\n    }\n    int palindromePartition(string s, int k) {\n        memset(dp, -1, sizeof(dp));\n        return rec(s, 0, 0, k);\n    }\n};\n```
['Dynamic Programming', 'Recursion', 'C++']