[Java] DP solution evolve from O(N^3*K) to O(N^2*K)
1.time complexity O(N^3K), space complexity O(NK) \n\nuse a function to calculate min changes required to transform string s[i,j] to a parlindrome\ndp[i][j] mea
1.time complexity O(N^3K), space complexity O(NK) \n\nuse a function to calculate min changes required to transform string s[i,j] to a parlindrome\ndp[i][j] means the min number of chars need to be changed to divide the string s[0,i] into j parlindromes\n```\n    public int palindromePartition(String s, int k) {\n        int n = s.length();\n        int[][] dp = new int[n][k+1];\n        for(int i=0; i<n; i++){\n            dp[i][1] = minChanges(s, 0, i);\n        }\n        \n        for(int i=1; i<n; i++){\n            for(int j=2; j<=Math.min(n,k); j++){\n                int min = Integer.MAX_VALUE;\n                for(int l=0; l<i; l++){\n                    min = Math.min(min, dp[l][j-1] + minChanges(s, l+1, i));\n                }\n                dp[i][j] = min==Integer.MAX_VALUE ? 0 : min;\n            }\n        }\n        \n        return dp[n-1][k];\n    }\n    \n    public int minChanges(String s, int i, int j){\n        int res = 0;\n        while(i<j){\n            if(s.charAt(i++)!=s.charAt(j--)){\n                res++;\n            }\n        }\n        return res;\n    }\n```\n\n2. time complexity O(N^2K), space complexity O(NK)\nprecalculate the min changes required to transform string s[i,j] to a parlindrome\n```\n    public int palindromePartition(String s, int k) {\n        int n = s.length();\n        //min changes to be parlindrome for string s[i,j]\n        int[][] minChanges = new int[n][n];\n        for(int i=0; i<n; i++){\n            for(int j=0; j<i; j++){\n                minChanges[j][i] = minChanges[j+1][i-1] + (s.charAt(j)==s.charAt(i) ? 0 : 1);\n            }\n        }\n        \n        int[][] dp = new int[n][k+1];\n        for(int i=0; i<n; i++){\n            dp[i][1] = minChanges[0][i];\n        }\n        \n        for(int i=1; i<n; i++){\n            for(int j=2; j<=Math.min(n,k); j++){\n                int min = Integer.MAX_VALUE;\n                for(int l=0; l<i; l++){\n                    min = Math.min(min, dp[l][j-1] + minChanges[l+1][i]);\n                }\n                dp[i][j] = min==Integer.MAX_VALUE ? 0 : min;\n            }\n        }\n        \n        return dp[n-1][k];\n    }\n```
[]