版权声明:本文为博主原创文章,遵循 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份的值就行。