JAVA | Memoization | Front-Row Partition Algorithm | EASY Approach
\tclass Solution {\n\t\tpublic int[][] dp;\n\t\tpublic int minCost(int i, int j, String s){\n\t\t\tint diff = 0;\n\t\t\twhile(i<j){\n\t\t\t\tif(s.charAt(i) != s
\tclass Solution {\n\t\tpublic int[][] dp;\n\t\tpublic int minCost(int i, int j, String s){\n\t\t\tint diff = 0;\n\t\t\twhile(i<j){\n\t\t\t\tif(s.charAt(i) != s.charAt(j))\n\t\t\t\t\tdiff++;\n\t\t\t\ti++;\n\t\t\t\tj--;\n\t\t\t}\n\t\t\treturn diff;\n\t\t}\n\t\tpublic int partition(int i, int k, int n, String s){\n\t\t\tif(i==n || k<0) return (int)1e9;\n\t\t\tif(k==0){\n\t\t\t\treturn minCost(i, s.length()-1, s);\n\t\t\t}\n\t\t\tif(dp[i][k] != -1) return dp[i][k];\n\n\t\t\tint min = n;\n\t\t\tfor(int index=i; index<n; index++){\n\t\t\t\tint value = minCost(i, index, s);\n\t\t\t\tint cost = value + partition(index+1, k-1, n, s);\n\t\t\t\tmin = Math.min(min, cost);\n\t\t\t}\n\t\t\treturn dp[i][k] = min;\n\t\t}\n\t\tpublic int palindromePartition(String s, int k) {\n\t\t\tint n = s.length();\n\n\t\t\tdp = new int[n+1][k+1];\n\t\t\tfor(int[] row: dp)\n\t\t\t\tArrays.fill(row, -1);\n\n\t\t\treturn partition(0, k-1, n, s);\n\t\t}\n\t}
['Dynamic Programming', 'Memoization', 'Java']