Simple C++ Bottom Up DP Explanation
The Main Idea here is to first pre compute the cost of converting Substring S[i..j] to palindrome & store it a matrix ,which \nwill be used in the main step for
The Main Idea here is to first pre compute the cost of converting Substring S[i..j] to palindrome & store it a matrix ,which \nwill be used in the main step for finding the answer\n\nNow let dp[idx][p] denote the min cost for dividing the substring s[idx...n-1] into p substrings such that each of these p substrings is a palindrome ( Here the subproblem is a sufffix array,Integer P (partitions) )\nSo Create a Dp Matrix of dimensions nxk & initialize each cell in it to a large value\nTrivial Cases\n1) When k=1 (in the matrix 0 based indexing is used): dp[i][0]=cost[i][n-1] ( calculated  from step 1)\n2) When number of partitions to be made is greater than suffix array partitions (it cant be possible so, Just leave them or set them to some higher value)\n  \n   Here now recurrence formula is\n    dp[i][p] =min(dp[j][p-1]) for all j->[i+1..n-1]\n\nFiiling of the DP table: You can fill it either column wise (starting from first col (bottom left cell)\nor You can fill it in the Row wise direction (starting from the bottom most row) (which I have used in my code)\n\nP.S: If you have any approach better than this, please comment below!\nCheers!\n```\nclass Solution {\npublic:\n    int palindromePartition(string s, int k) {\n        //the idea here is to first pre compute the cost of converting sbstring s[i..j] into palidrome\n        //this cost table will be used in the step 2\n        \n        int n=s.length();\n        vector<vector<int>> cost(n,vector<int>(n,0));\n         //cost for converting all single length substrings into palindrome is 0, as they are already palindrome\n        //for s[i..j] it is if(s[i]==s[j])then cost[i][j]=cost[i+1][j-1] else 1+cost[i+1][j-1]\n       \n        for(int i=1;i<n;i++){\n          for(int j=0;j<n-i;j++){\n              //j,j+i\n              if(s[j]==s[j+i]){\n                  cost[j][j+i]=cost[j+1][j+i-1];\n              }\n              else{\n                  cost[j][j+i]=1+cost[j+1][j+i-1];\n              }\n          }    \n        }\n        \n        vector<vector<int>> dp(n,vector<int>(k,1000));\n        for(int i=0;i<n;i++){\n            dp[i][0]=cost[i][n-1];\n        }\n        for(int i=n-1;i>=0;i--){\n            for(int j=1;j<k;j++){//already pre computed for j=0, i.e single partiton only\n                 int partitions=j+1;\n                if(n-i<partitions) break;\n                \n                //else means that suffix substring s[i..n-1] can be divided into j+1 partitons\n                int idx=i;\n                while(idx+1<n){\n                    int a=cost[i][idx];\n                    int b=dp[idx+1][j-1];\n                    dp[i][j]=min(dp[i][j],a+b);\n                    idx++;\n                }\n            }\n        }\n        return dp[0][k-1];\n    }\n};\n```
[]