[Java] Bottom Up DP Solution With Video Explanation
\n\n\nclass Solution {\n    \n    HashMap<String, Integer> cache = new HashMap<>();\n    \n    public int palindromePartition(String s, int k) {\n        String
<iframe width="560" height="315" src="https://www.youtube.com/embed/Oqkp2MfFpMA" frameborder="0" allow="accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>\n\n```\nclass Solution {\n    \n    HashMap<String, Integer> cache = new HashMap<>();\n    \n    public int palindromePartition(String s, int k) {\n        String key = s +","+k;\n        if(cache.containsKey(key)) return cache.get(key);\n        if(k == 1) {\n            int c = 0;\n            for(int i = 0; i < s.length() / 2; i++) {\n                if(s.charAt(i) != s.charAt(s.length() - 1 - i)) {\n                    c++;\n                }\n            }\n            return c;\n        }\n        int output = Integer.MAX_VALUE;\n        for(int kk = 1; kk < k; kk++) {\n            for(int i = 1; i <= s.length() - (k - kk); i++) {\n                String sub1 = s.substring(0, i);\n                String sub2 = s.substring(i);\n                if(i >= kk) {\n                    int left = palindromePartition(sub1, kk);\n                    int right = palindromePartition(sub2, k - kk);\n                    output = Math.min(output, left + right);\n                } else {\n                    break;\n                }\n            }\n        }\n        cache.put(key, output);\n        return output;\n    }\n}\n```
['Dynamic Programming']