C++ dp beats 100%
Firstly, thanks @zhutianqi. This answer is based on c++ dp O(kn^2) . \nIn the competition, I try to use the memory recursion method. But always wrong answer. \n
Firstly, thanks @zhutianqi. This answer is based on [c++ dp O(kn^2) ](https://leetcode.com/problems/palindrome-partitioning-iii/discuss/441391/c%2B%2B-dp-O(kn2)). \nIn the competition, I try to use the memory recursion method. But always wrong answer. \nThe question requests us to calculate palindromePartition( s[0...end], k ). \nThis problem is obviously equal to `min { change_to_palindrome( s[0...d] ) + palindromePartition( s[d+1...end], k-1 ) }`\nSo, we can define two dp array to record `change_to_palindrome( s[0...d] )` and `palindromePartition( s[d+1...end], k-1 )`\n```\nint change[110][110];   // change[i][j] is the number of change s[i...j] to Palindrome\nint dp[110][110];       // dp[i][k] is the result of palindromePartition(s[i...end], k)\n```\n\nThe initialization of the `change` array is\n```\nmemset(change, 0, sizeof(change));   // obviously change[i][i] = 0\nfor (int len = 2; len <= n; ++len) {   // the length between i and j\n\tfor (int i = 0; i + len <= n; ++i) {\n\t\tint j = i + len - 1;\n\t\tif (s[i] == s[j])\n\t\t\tchange[i][j] = change[i+1][j-1];\n\t\telse\n\t\t\tchange[i][j] = change[i+1][j-1] + 1;\n\t}\n}\n```\n\nThe initialization of the `dp` array is\n```\nfor (int i = 0; i < n; ++i)\n\t  dp[i][1] = change[i][n-1];\n```\n\nThe recursive expression is\n```\nfor (int d = 2; d <= k; ++d) {\n\tfor (int i = 0; i < n; ++i) {\n\t\tdp[i][d] = INT_MAX;   \n\t\tfor (int j = i; j < n; ++j)\n\t\t\tdp[i][d] = min(dp[i][d], change[i][j] + dp[j+1][d-1]);\n\t}\n}\n```\n\nThe complete code is as follows\n```\nclass Solution {\npublic:\n    int palindromePartition(string s, int k) {\n        int change[110][110];  // number of change s[i...j] to Palindrome\n        int dp[110][110];    // result of palindromePartition(s[i...end], k)\n        int n = s.size();\n        memset(change, 0, sizeof(change));\n        memset(dp, 0, sizeof(dp));\n        \n        for (int len = 2; len <= n; ++len) {\n            for (int i = 0; i + len <= n; ++i) {\n                int j = i + len - 1;\n                \n                if (s[i] == s[j])\n                    change[i][j] = change[i+1][j-1];\n                else\n                    change[i][j] = change[i+1][j-1] + 1;\n            }\n        }\n        \n        for (int i = 0; i < n; ++i)\n            dp[i][1] = change[i][n-1];\n        \n        \n        for (int d = 2; d <= k; ++d) {\n            for (int i = 0; i < n; ++i) {\n                dp[i][d] = INT_MAX;   \n                for (int j = i; j < n; ++j)\n                    dp[i][d] = min(dp[i][d], change[i][j] + dp[j+1][d-1]);\n                \n                \n            }\n        }\n        return dp[0][k];\n    }\n};\n```\n\n**Result**\nRuntime: 8 ms, faster than 100.00% of C++ online submissions for Palindrome Partitioning III.\nMemory Usage: 8.4 MB, less than 100.00% of C++ online submissions for Palindrome Partitioning III.\n
[]