[C++] Palindrome Partitioning All Variations
Do Upvote if it helps :-)\n\nMUST CHECK->\nBest Time to Buy and Sell Stock All Variations\uD83D\uDC49Click Me\n\n131. Palindrome Partitioning I\n\n\tclass Solut
**Do Upvote if it helps :-)**\n\n**MUST CHECK->**\n**Best Time to Buy and Sell Stock All Variations\uD83D\uDC49**[Click Me](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/discuss/2237933/C%2B%2B-Best-Time-to-Buy-and-Sell-Stock-All-Variations-Recursion%2BMemoization)\n\n[131. Palindrome Partitioning I](https://leetcode.com/problems/palindrome-partitioning/)\n\n\tclass Solution {\n\tpublic:\n\t\tvector<vector<string>>ans;\n\t\tbool isPali(string s,int l,int r){\n\t\t\twhile(l<r){\n\t\t\t\tif(s[l]!=s[r]){\n\t\t\t\t\treturn false;\n\t\t\t\t}\n\t\t\t\tl++;\n\t\t\t\tr--;\n\t\t\t}\n\t\t\treturn true;\n\t\t}\n\t\tvoid check(int ind,string &s,vector<string> &cur){\n\t\t\tif(ind==s.size()){\n\t\t\t\tans.push_back(cur);\n\t\t\t\treturn ;\n\t\t\t}\n\t\t\tfor(int i=ind;i<s.size();i++){\n\t\t\t\tif(isPali(s,ind,i)){\n\t\t\t\t\tcur.push_back(s.substr(ind,i-ind+1));\n\t\t\t\t\tcheck(i+1,s,cur);\n\t\t\t\t\tcur.pop_back();\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t\tvector<vector<string>> partition(string s) {\n\t\t\tvector<string>cur;\n\t\t\tcheck(0,s,cur);\n\t\t\treturn ans;\n\t\t}\n\t};\n\t\n[132. Palindrome Partitioning II](https://leetcode.com/problems/palindrome-partitioning-ii/)\n\n\tclass Solution {\n\tpublic:\n\t\tvector<int> dp;\n\t\tint isPali(string &s,int l,int r){\n\t\t\twhile(l<r){\n\t\t\t\tif(s[l++]!=s[r--]) return false;\n\t\t\t}\n\t\t\treturn true;\n\t\t}\n\t\tint solve(string &s,int pos,int n){\n\t\t\tif(pos>=n  || isPali(s,pos,n)) return 0;\n\t\t\tif(dp[pos]!=-1) return dp[pos];\n\t\t\tint ans=0,tmp=INT_MAX;\n\t\t\tfor(int i=pos;i<n;i++){\n\t\t\t\tif(isPali(s,pos,i)){\n\t\t\t\t\tans=1+solve(s,i+1,n);\n\t\t\t\t\ttmp=min(tmp,ans);\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn dp[pos] = tmp;\n\t\t}\n\t\tint minCut(string s) {\n\t\t\tdp.assign(s.size(),-1);\n\t\t\treturn solve(s,0,s.size())-1;\n\t\t}\n\t};\n\t\n[1278. Palindrome Partitioning III](https://leetcode.com/problems/palindrome-partitioning-iii/)\n\n\tclass Solution {\n\tpublic:\n\t\tvector<vector<int>> cost;\n\t\tint costFun(string &s,int l,int r){\n\t\t\tif(l>=r) return 0;\n\t\t\tif(cost[l][r]!=-1) return cost[l][r];\n\t\t\treturn cost[l][r] = (s[l]!=s[r]) + costFun(s,l+1,r-1);\n\t\t}\n\n\t\tvector<vector<int>>dp;\n\t\tint solve(string &s,int k,int pos,int n){\n\t\t\tif(k==0) return costFun(s,pos,n-1);\n\t\t\tif(pos>=n) return INT_MAX;\n\t\t\tif(dp[pos][k]!=-1) return dp[pos][k];\n\t\t\tint ans=1e6;\n\t\t\tfor(int i=pos;i<n-1;i++){\n\t\t\t\tans=min(ans,costFun(s,pos,i)+solve(s,k-1,i+1,n));\n\t\t\t}\n\t\t\treturn dp[pos][k] = ans;\n\t\t}\n\t\tint palindromePartition(string s, int k) {\n\t\t\tint n=s.size();\n\t\t\tcost.assign(n,vector<int>(n,-1));\n\t\t\tdp.assign(n,vector<int>(k+1,-1));\n\t\t\treturn solve(s,k-1,0,n);\n\t\t}\n\t};\n\t\n[1745. Palindrome Partitioning IV](https://leetcode.com/problems/palindrome-partitioning-iv/)\n\n\tclass Solution {\n\tpublic:\n\t\tvector<int> dp;\n\t\tvector<vector<int>> pali;\n\t\tint isPali(string &s,int l,int r){\n\t\t\tif(l>=r) return 1;\n\t\t\tif(pali[l][r]!=-1) return pali[l][r];\n\t\t\tif(s[l]==s[r]) return pali[l][r] = isPali(s,l+1,r-1);\n\t\t\treturn pali[l][r] = 0;\n\t\t}\n\n\t\tbool checkPartitioning(string s) {\n\t\t\tint n=s.size();\n\t\t\tpali.assign(n,vector<int>(n,-1));\n\t\t\tfor(int i=1;i<n-1;i++){\n\t\t\t\tfor(int j=1;j<=i;j++){\n\t\t\t\t\tif(isPali(s,0,j-1) && isPali(s,j,i) && isPali(s,i+1,n-1)) return true;\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn false;\n\t\t}\n\t};
['Dynamic Programming', 'Memoization', 'C', 'C++']