Step by Step solution DP (Java)
There are a lot of these types of questions in DP Hard. If you learn to recognize the basic structure, you can come up with an answer fairly quickly.\nCouple wo
There are a lot of these types of questions in DP Hard. If you learn to recognize the basic structure, you can come up with an answer fairly quickly.\nCouple words that give away the DP nature of the problem\n1. Palindrome \n1. Minimum \n\nIf we break the question apart we get:\n1. How many changes do I need to perform to make S.substring(i, j) to a palindrome.\n1. How many ways can I split the string from i to j into groups and what are their costs.\n1. What is the minimum combination of these groups.\n\nFirst thing you should make is a map that contains all the cost from i to j\nThis is faily simple given the nature of substituion.\n```\n\t\t...\n        int[][] toPal = new int[s.length()][s.length()];\n        for (int i = 0; i < s.length(); i++) {\n            toPal[i][i] = 0;\n        }\n        for (int i = s.length()-1; i >= 0; i--) {\n            for (int j = i + 1; j < s.length(); j++) {\n                toPal[i][j] = getChanges(s, i, j);\n            }\n        }\n\t\t...\n\t}\n    private int getChanges(String s, int start, int end) {\n        int changes = 0;\n        while(start < end) {\n            if (s.charAt(start++) != s.charAt(end--)) {\n                changes++;\n            }\n        }\n        return changes;\n    }\n```\n*So now if i want to know how many substitution I need to make s.substring(i,j) into an palindrome then I can just do toPal[i][j]*\n\nSecond I want to define my dp problem through some sort of an equation. \nGiven: aabbcc, k = 3\nThe possible groups can be\n\n(aabb)(c)(c), (aab)(bc)(c), (aa)(bbc)(c),  (a)(abbc)(c) -**(third group is (c))**\n(aab)(b)(cc), (aa)(bb)(cc), (aa)(bb)(cc) --------------**(third group is (cc))**\n(aa)(b)(bcc), (a)(ab)(bcc) ---------------------------**(third group is (bcc))**\n(a)(a)(bbcc) ----------------------------------------**(third group is (bbcc))**\n\n\nThird, notice that there is 4 different ways have third group be just (c). 3 ways for (cc). 2 ways for (bcc). and 1 way for (bbcc). \n```\ndp[k][end]\nmin((aabb)(c), (aab)(bc), (aa)(bbc), (a)(abbc)) = dp[2][4]\nor dp[2][4] = Math.min(toPal[0][3] + toPal[4][4], toPal[0][2] + toPal[3][4], toPal[0][1] + toPal[2][4], toPal[0][0] + toPal[1][4])\nmin((aab)(b), (aa)(bb), (aa)(bb)) = dp[2][3]\nor dp[2][3] = Math.min(toPal[0][2] + toPal[3][3], toPal[0][1] + toPal[2][3], toPal[0][0] + toPal[1][3])\nmin((aa)(b), (a)(ab)) = dp[2][2]\nor dp[2][2] = Math.min(toPal[0][1] + toPal[2][2], toPal[0][0] + toPal[1][2])\nmin((a)(a)) = dp[2][1]\nor dp[2][1] = toPal[0][0] + toPal[1][1]\n```\nSo:\n\n```\ndp[3][5] // this our answer because we want 3rd group to end at index 5\ndp[3][5] = Math.min(dp[2][4] + toPal[5][5], dp[2][3] + toPal[4][5], dp[2][2] + toPal[3][5], dp[2][1] + toPal[2][5])\n```\nAns:\n```\nclass Solution {\n    public int palindromePartition(String s, int k) {\n        int[][] toPal = new int[s.length()][s.length()];\n        int[][] dp = new int[k+1][s.length()];\n        for (int i = 0; i < s.length(); i++) {\n            toPal[i][i] = 0;\n        }\n        for (int i = s.length()-1; i >= 0; i--) {\n            for (int j = i + 1; j < s.length(); j++) {\n                toPal[i][j] = getChanges(s, i, j);\n            }\n        }\n        for (int i = 0; i < s.length(); i++) {\n            dp[1][i] = toPal[0][i];\n        }\n        for (int i = 2; i <= k; i++) {\n            for (int end = i-1; end < s.length(); end++) {\n                int min = s.length();\n                for (int start = end-1; start >= i-2; start--) {\n                    min = Math.min(min, dp[i-1][start] + toPal[start+1][end]);\n                }\n                dp[i][end] = min;\n            }\n        }\n        return dp[k][s.length()-1];\n    }\n    \n    \n    private int getChanges(String s, int start, int end) {\n        int changes = 0;\n        while(start < end) {\n            if (s.charAt(start++) != s.charAt(end--)) {\n                changes++;\n            }\n        }\n        return changes;\n    }\n}\n```\n\n\n
[]