Java DP with Memorization beats 100% java soltions
\nclass Solution {\n    public int helper(int[][] change,String s,int end,int k,Integer[][] dp){\n        if(k == end) return 0;\n        if(k == 1) return chan
```\nclass Solution {\n    public int helper(int[][] change,String s,int end,int k,Integer[][] dp){\n        if(k == end) return 0;\n        if(k == 1) return change[0][end-1];\n        if(dp[end][k] != null) return dp[end][k];\n        int ans = Integer.MAX_VALUE;\n        for(int i = k-1;i < end;i++){\n            ans = Math.min(ans,helper(change,s,i,k-1,dp)+change[i][end-1]);\n        }\n        return dp[end][k] = ans;\n    }\n    public int palindromePartition(String s, int k) {\n        int n = s.length();\n        int[][] dp = new int[n][n];\n        for(int g = 0;g<n;g++){\n            for(int i = 0,j = g;j < n;i++,j++){\n                if(g == 0) dp[i][j] = 0;\n                else if(g == 1){\n                    if(s.charAt(i) == s.charAt(j)) dp[i][j] = 0;\n                    else dp[i][j] = 1;\n                }else{\n                    if(s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1];\n                    else dp[i][j] = 1+dp[i+1][j-1];\n                }\n            }\n        }\n        return helper(dp,s,n,k,new Integer[n+1][k+1]);\n    }\n}\n```
[]