C++ 4ms Short Top-Down DP with Explanation
This is a variation of well known problem of Dynamic Programming viz. MCM (Matrix Chain Multiplication). \n\nLets analyze the brute-force approach first. This p
This is a variation of well known problem of Dynamic Programming viz. MCM (Matrix Chain Multiplication). \n\nLets analyze the brute-force approach first. This problem can be divided into 2 sections:\n1. Partitioning the given string ```s``` into all possible ```k``` different substrings.\n2. Finding the lowest cost of partitioning among all possible substrings partitions.\n\n**Lets go on to understand how to accomplish it**\n* Our goal is to write logic to partition a single string to 2 different substrings, and then call the function recursively to get ```k``` partitions.\n* **Inductive Step:** So, for a string ```S[i...n-1]```, we can split it into ```[i..part]``` and ```[part+1, n-1]```.\n* For, each recursive step, we add the cost ```C[i...part]``` and pass on the control to next recursive calls to add up cost of the 2nd part till it gets partitioned into ```k``` substrings overall.\n* **Base Case:** When the no. of substrings adds up to ```k```, then we return the cost. Otherwise, if the iterator reaches the end with less than ```k``` partitions, its not possible hence return ```INFINITY``` (in this case 105, since the max. value of k is 99 because ```size(String) <= 100```). \n\n* Since calculating Cost would take O(n) time everytime, we need to decrease the amortized time complexity by memoizing the Cost using ```C[i][j]```, where ```C[i][j]``` signifies the cost of making the substring ```S[i...j]``` palindrome. \n\n\n```\nclass Solution {\npublic:\n    int dp[101][101], C[101][101];\n    const int inf = 1e2+5;\n    \n    int cost(string& s, int i, int j){\n        if(i >= j) return 0;\n        if(C[i][j] != -1) return C[i][j];\n        return C[i][j] = (s[i] != s[j]) + cost(s, i+1, j-1);\n    }\n    \n    int partition(string& s, int i, int k){\n        if(k == 0) return cost(s, i, s.size()-1);\n        if(i == s.size()) return inf;\n        \n        if(dp[i][k] != -1) return dp[i][k];\n        \n        int ans = inf;\n        for(int part=i; part<s.size()-1; part++){\n            ans = min(ans, cost(s, i, part) + partition(s, part+1, k-1));\n        }\n        \n        return dp[i][k] = ans;\n    }\n    \n    int palindromePartition(string s, int k) {\n        memset(C, -1, sizeof(C));\n        memset(dp, -1, sizeof(dp));\n        \n        return partition(s, 0, k-1);\n    }\n};\n```\n\nPlease upvote it if you liked it !!! This will encourage me to write more posts. :)
['Dynamic Programming', 'Memoization', 'C']