2-State dp solution || Top Down approach || java
class Solution {\n    \n    int inf=100000000;\n    int[][] dp;\n    \n    public int palindromePartition(String s, int k) {\n        \n        if(s.length()==k
class Solution {\n    \n    int inf=100000000;\n    int[][] dp;\n    \n    public int palindromePartition(String s, int k) {\n        \n        if(s.length()==k)return 0;\n        \n        dp=new int[s.length()+1][k+1];\n        \n        for(int i=0;i<=s.length();i++){// intialize dp states with -1\n            int[] temp=new int[k+1];\n            Arrays.fill(temp,-1);\n            dp[i]=temp;\n        }\n        \n        int ans=minCost(s,0,k);\n        return ans;\n        \n        \n    }\n    public int minCost(String str,int i,int k){\n        if(i>=str.length() || k<=0){ // if i reach to its end length OR no partision left to do so\n            if(i>=str.length() && k==0)return 0;\n            return inf;\n\n        }\n        if(dp[i][k]!=-1)return dp[i][k];// if already computed no need to compute again\n       int ans=inf;\n\n       for(int j=i;j<str.length();j++){//doing partision from ith to jth\n           \n           String s=str.substring(i,j+1);// substring from ith to jth\n           \n           int v=charRequire(s);// getting up the number of unequal character\n           int q1=v+minCost(str,j+1,k-1);\n           \n           ans=Math.min(ans,q1);// try to find minimum answer possible\n       }\n       return dp[i][k]=ans;// putting up value in dp states\n    }\n    \n    \n    public int charRequire(String str){\n        // this method used to get number of unequal character\n        \n        int i=0,j=str.length()-1;\n        \n        int count=0;\n        while(i<=j){\n            if(str.charAt(i)!=str.charAt(j))count++;\n            i++;\n            j--;\n        }\n        return count;\n    }\n}
[]