【未完成】【leetcode第 165 场周赛】分割回文串 III

版权声明：本文为博主原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/shiliang97/article/details/103334502

5278. Palindrome Partitioning III

You are given a string s containing lowercase letters and an integer k. You need to :

First, change some characters of s to other lowercase English letters. Then divide s into k non-empty disjoint substrings such that each substring is palindrome. Return the minimal number of characters that you need to change to divide the string.

Example 1:

Input: s = "abc", k = 2 Output: 1 Explanation: You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome. Example 2:

Input: s = "aabbc", k = 3 Output: 0 Explanation: You can split the string into "aa", "bb" and "c", all of them are palindrome. Example 3:

Input: s = "leetcode", k = 8 Output: 0

Constraints:

1 <= k <= s.length <= 100. s only contains lowercase English letters.

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-partitioning-iii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题，考的时候不会，所以我来分析一下这个第一的美国老哥的代码

人家三分钟就写完了~~~~我题目都看了十分钟。。。

暴力递归+记忆化

const int N_MAX = 105;
const int INF = 1e9 + 5;

class Solution {
public:
    int dp[N_MAX][N_MAX];

    int palindromePartition(string s, int k) {
        int n = s.size();

        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= k; j++)
                dp[i][j] = INF;

        dp[0][0] = 0;
        //i是长度到i,j是分成了j段
        for (int i = 0; i < n; i++)
            for (int j = 0; j < k; j++)
                for (int len = 1; i + len <= n; len++) {
                    int cost = 0;//cost 是需要转换的个数

                    for (int a = i, b = i + len - 1; a < b; a++, b--)
                        cost += s[a] != s[b];//把需要换的部分换了

                    dp[i + len][j + 1] = min(dp[i + len][j + 1], dp[i][j] + cost);//比较是否需要更新
                }

        return dp[n][k];
    }
};

感觉也是暴力，但是中间一直在更新最小值。

最后找到长度N，分成K份的值就行。