Partition DP || Recursion || Memoization || DP
Intuition\nThis problem is very Similar to Palindrome Partitioning II, where we need to partition the given string into palindromes with minimum cuts, I\'ll pro
# Intuition\nThis problem is very Similar to [Palindrome Partitioning II](https://leetcode.com/problems/palindrome-partitioning-ii/), where we need to partition the given string into palindromes with minimum cuts, I\'ll provide my solution with streamline explaination for that problem here: [Solution](https://leetcode.com/problems/palindrome-partitioning-ii/solutions/3838499/partition-dp-recursion-memoization-bottum-up-solution/).\n\nNow Let\'s dive into current problem, question states that we need to make `k` partitions in the string such that all the partitioned strings need less cost to get converted into palindrome.\n\nAt first I didn\'t get what he meant until i looked up a testcase:\n`"abc" and k = 2`, we need to split the given string into k substrings, i.e., into 2 substrings here, now this can be done in 2 ways: \n- `"ab" & "c"`\n- `"a" & "bc"`\n\nHere both ways have substrings having `1` **palindrome** and the other not, we can convert that **non-palindrome** to **palindrome** which is the required cost we needed to minimize, that is we need to convert `ab` or `bc` to palindrome, this can be done by replacing\n-  `b` in `ab` with `a` thereby converted to `aa` or vice-versa.\n-  `b` in `bc` with `c` thereby converted to `cc` or vice-versa.\n\nEither of them are fine since both of them are costing us 1 conversion thereby our **minimum cost = 1**. \n\n# Approach\nHere we apply Recursion to partition our string at each index *(say state)* with keeping no. of partitions `(k)` in mind. \n\n# Code: Recursion\n```\nclass Recursion {\nprivate:\n    int n;\n    int getCost(string& s, int l, int r)\n    {\n        int cost = 0; \n        while(l < r)\n        {\n            if(s[l++] != s[r--])\n            {\n                cost++;\n            }\n        }\n        return cost;\n    }\n    int solve(string& s, int idx, int partitions)\n    {\n        if(idx >= n)\n        {\n            return 0;\n        }\n        if(partitions == 0)\n        {\n            return getCost(s, idx, n-1);\n        }\n        int minCost = 102;  // Since as mentioned the maxStringLength = 100 so maintaining minCost as 102 instead of INT_MAX\n        for(int k=idx; k<n-1; k++)\n        {\n            int cost = getCost(s, idx, k) + solve(s, k+1, partitions-1);\n            minCost = min(minCost, cost);\n        }\n        return minCost;\n    }\npublic:\n    int palindromePartition(string s, int k) {\n        n = s.size();\n        return solve(s, 0, k-1);\n    }\n};\n```\n\n# Complexity\n- Time complexity: We already know that for recursion it is $$O(2^N)$$ as there are two changing states `idx` and `k` where k is equivalent to `N` as mentioned, and at each state we are trying to check if it is a palindrome or not which at worst case has $$O(N)$$,\nSo total Time Complexity is $$O(N*2^N)$$.\n\n- Space complexity: $$O(N^2)$$ Recursion stack space\n\n# Code: Top-Down Dynamic Programming (Memoization)\n```\nclass RecMemo {\nprivate:\n    int n;\n    int memo[100][100];\n    int getCost(string& s, int l, int r)\n    {\n        int cost = 0; \n        while(l < r)\n        {\n            if(s[l++] != s[r--])\n            {\n                cost++;\n            }\n        }\n        return cost;\n    }\n    int solve(string& s, int idx, int partitions)\n    {\n        if(idx >= n)\n        {\n            return 0;\n        }\n        if(partitions == 0)\n        {\n            return getCost(s, idx, n-1);\n        }\n        if(memo[idx][partitions] != -1)\n        {\n            return memo[idx][partitions];\n        }\n        int minCost = 102;\n        for(int k=idx; k<n-1; k++)\n        {\n            int cost = getCost(s, idx, k) + solve(s, k+1, partitions-1);\n            minCost = min(minCost, cost);\n        }\n        return memo[idx][partitions] = minCost;\n    }\npublic:\n    int palindromePartition(string s, int k) {\n        n = s.size();\n        memset(memo, -1, sizeof(memo));\n        return solve(s, 0, k-1);\n    }\n};\n```\n# Complexity\n- Time complexity: $$O(N^3)$$, As for each call we have two states `idx` and `k` i.e., $$O(N^2)$$ and at each state we are checking for palindrome which is $$O(N)$$.\n\n- Space complexity: $$O(N^2) + O(N^2)$$ Memo Array + Recursion stack space.\n\n# Code: Bottum-up Dynamic Programming\n```\nclass DP {\nprivate:\n    int getCost(string& s, int l, int r)\n    {\n        int cost = 0; \n        while(l < r)\n        {\n            if(s[l++] != s[r--])\n            {\n                cost++;\n            }\n        }\n        return cost;\n    }\npublic:\n    int palindromePartition(string s, int k) {\n        int n = s.size();\n        vector<vector<int>> dp(n+1, vector<int>(k));\n        for(int partition=0; partition<k; partition++)\n        {\n            dp[n][partition] = 0;\n        }\n        for(int i=0; i<n; i++)\n        {\n            dp[i][0] = getCost(s, i, n-1);\n        }\n        for(int i=n-1; i>=0; i--)\n        {\n            for(int partition=1; partition<k; partition++)\n            {\n                int minCost = 102;\n                for(int k=i; k<n-1; k++)\n                {\n                    int cost = getCost(s, i, k) + dp[k+1][partition-1];\n                    minCost = min(minCost, cost);\n                }\n                dp[i][partition] = minCost;\n            }\n        }\n        return dp[0][k-1];\n    }\n};\n```\n# Complexity\n- Time complexity: $$O(N^3)$$, As for each call we have two states `idx` and `k` i.e., $$O(N^2)$$ and at each state we are checking for palindrome which is $$O(N)$$.\n\n- Space complexity: $$O(N^2)$$ DP Array.\n\n![naruto.gif](https://assets.leetcode.com/users/images/107541cf-e34e-43d9-a4a6-74d81405390b_1690722278.793266.gif)\n\n\nHope you understood this Solution, Just in case you understod please Upvote and share this Awesome question with your fellow coders.\n\n# All Palindrome-Partitioning Questions & Solutions Package\n- [Palindrome Partitioning I](https://leetcode.com/discuss/topic/3838399/simple-recursion-backtracking/)\n- [Palindrome Partitioning II](https://leetcode.com/discuss/topic/3838499/partition-dp-recursion-memoization-bottum-up-solution/)\n- [Palindrome Partitioning III](https://leetcode.com/discuss/topic/3838605/partition-dp-recursion-memoization-dp/)\n- [Palindrome Partitioning IV](https://leetcode.com/discuss/topic/3838671/partition-dp-recursion-memoization-dp/)\n\nWith this I\'m Signing off.\n\n![minato.gif](https://assets.leetcode.com/users/images/cf401779-a908-41c5-a1b7-b9a22a3eb3a3_1690722295.4293869.gif)
['String', 'Dynamic Programming', 'Recursion', 'Memoization', 'C++']