Nothing in this world that is worth having comes easy.
這世界上凡是值得擁有的東西，都不易獲得。
問題描述
來(lái)源：LeetCode第1278題
難度：困難
給你一個(gè)由小寫字母組成的字符串s，和一個(gè)整數(shù)k。
請(qǐng)你按下面的要求分割字符串：
首先，你可以將s中的部分字符修改為其他的小寫英文字母。
接著，你需要把s分割成k個(gè)非空且不相交的子串，并且每個(gè)子串都是回文串。
請(qǐng)返回以這種方式分割字符串所需修改的最少字符數(shù)。
示例 1：
輸入：s = "abc", k = 2
輸出：1
解釋：你可以把字符串分割成 "ab" 和 "c"，并修改 "ab" 中的 1 個(gè)字符，將它變成回文串。
示例 2：
輸入：s = "aabbc", k = 3
輸出：0
解釋：你可以把字符串分割成 "aa"、"bb" 和 "c"，它們都是回文串。
示例 3：
輸入：s = "leetcode", k = 8
輸出：0
提示：
1 <= k <= s.length <= 100
s 中只含有小寫英文字母。
動(dòng)態(tài)規(guī)劃解決
這題是讓通過修改一些字符把字符串分割為k個(gè)子串，并且每個(gè)子串都是回文的，問最少修改的字符數(shù)。
最容易想到的就是把字符串s分割k個(gè)子串的所有可能組合，然后計(jì)算每個(gè)組合中子串變成回文串修改字符的數(shù)量，最后返回最小的即可。比如示例二中我們可以分割為
但是當(dāng)字符串s比較長(zhǎng)的時(shí)候，運(yùn)行效率是很差的。這里我們可以使用動(dòng)態(tài)規(guī)劃來(lái)解決，定義dp[i][j]表示表示字符串s的前i個(gè)字符分割為j個(gè)子串的修改的最小字符數(shù)。很明顯i必須大于等于j，要不然不可能分割為j個(gè)子串。
動(dòng)態(tài)規(guī)劃最關(guān)鍵的是找出遞推公式，當(dāng)我們要求dp[i][j]的時(shí)候，只需要找出前m個(gè)字符分割成j-1個(gè)子串所修改的最小字符數(shù)+最后一個(gè)子串所需要修改字符數(shù)。（最后一個(gè)子串就是前i個(gè)字符-前m個(gè)字符），看到這里大家是不是很容易想到比較經(jīng)典的基礎(chǔ)背包問題，前面也有講過371，背包問題系列之-基礎(chǔ)背包問題，其中還有多重背包和完全背包這些我們以后會(huì)再講。
所以遞推公式我們很容易想到
dp[i][j]=dp[m][j-1]+change(s,m,i-1);
這里我們需要枚舉m的值，但要注意m必須大于等于j-1，如下圖所示
這題要求的是返回最小的字符修改數(shù)，所以我們記錄最小的即可
dp[i][j] = Math.min(dp[i][j], dp[m][j - 1] + change(s, m, i - 1));其中change(s,m,i-1)表示字符串s[m,i-1]變成回文串所需要修改的字符數(shù)。他的代碼比較簡(jiǎn)單，我們來(lái)看下
1//字符串的子串[left,right]變成回文串所需要修改的字符數(shù)
2private int change(String s, int left, int right) {
3 int count = 0;
4 while (left < right) {
5 //如果兩個(gè)指針指向的字符相同，我們不需要修改。
6 //如果不相同，只需要修改其中的一個(gè)即可，所以
7 // 修改數(shù)要加1
8 if (s.charAt(left++) != s.charAt(right--))
9 count++;
10 }
11 return count;
12}
分析到這里，這題的代碼基本上就呼之欲出了，我們來(lái)看下完整代碼
1public int palindromePartition(String s, int k) {
2 int length = s.length();
3 //dp[i][j]表示s的前i個(gè)字符分割成k個(gè)子串所修改的最少字符數(shù)。
4 int[][] dp = new int[length + 1][k + 1];
5 //因?yàn)檫@題要求的是所需要修改的最少字符數(shù)，初始值我們賦值盡可能大
6 for (int i = 0; i < dp.length; i++) {
7 Arrays.fill(dp[i], length);
8 }
9 //前i個(gè)字符，分割成j個(gè)回文子串
10 for (int i = 1; i <= length; i++) {
11 //前i個(gè)字符最大只能分割成i個(gè)子串，所以不能超過i，
12 //我們?nèi)和k的最小值
13 int len = Math.min(i, k);
14 for (int j = 1; j <= len; j++) {
15 if (j == 1) {
16 //如果j等于1，則表示沒有分割，我們直接計(jì)算
17 dp[i][j] = change(s, j - 1, i - 1);
18 } else {
19 //如果j不等于1，我們計(jì)算分割所需要修改的最小字符數(shù)，因?yàn)閙的值要
20 //大于等于j-1，我們就從最小的開始枚舉
21 for (int m = j - 1; m < i; m++) {
22 //遞推公式
23 dp[i][j] = Math.min(dp[i][j], dp[m][j - 1] + change(s, m, i - 1));
24 }
25 }
26 }
27 }
28 //返回前l(fā)ength個(gè)字符分割成k個(gè)子串所需要修改的最少字符數(shù)
29 return dp[length][k];
30}
31
32//字符串的子串[left,right]變成回文串所需要修改的字符數(shù)
33private int change(String s, int left, int right) {
34 int count = 0;
35 while (left < right) {
36 //如果兩個(gè)指針指向的字符相同，我們不需要修改。
37 //如果不相同，只需要修改其中的一個(gè)即可，所以
38 // 修改數(shù)要加1
39 if (s.charAt(left++) != s.charAt(right--))
40 count++;
41 }
42 return count;
43}
動(dòng)態(tài)規(guī)劃代碼優(yōu)化
上面代碼中都有注釋，這里就不在過多介紹，我們來(lái)看一下change方法，因?yàn)檫@里會(huì)涉及到字符的重復(fù)計(jì)算，導(dǎo)致效率不高，我們可以先計(jì)算所有的子串變成回文串需要修改的字符數(shù)，然后再使用，來(lái)看下代碼
1public int palindromePartition(String s, int k) {
2 int length = s.length();
3
4 //palindrome[i][j]表示子串[i,j]轉(zhuǎn)化為回文串所需要的修改的字符數(shù)
5 int[][] palindrome = new int[length][length];
6 //2種實(shí)現(xiàn)方式
7 // //一列一列的從左往右（只遍歷右上部分）
8 // for (int j = 1; j < length; j++) {
9 // for (int i = 0; i < j; i++) {
10 // palindrome[i][j] = palindrome[i + 1][j - 1] + (s.charAt(i) == s.charAt(j) ? 0 : 1);
11 // }
12 // }
13
14 //一行一行的從下往上（只遍歷右上部分）
15 for (int i = length - 2; i >= 0; i--) {
16 for (int j = i + 1; j < length; j++) {
17 palindrome[i][j] = palindrome[i + 1][j - 1] + (s.charAt(i) == s.charAt(j) ? 0 : 1);
18 }
19 }
20
21 //dp[i][j]表示s的前i個(gè)字符分割成k個(gè)回文子串的最少次數(shù),
22 //第一行和第一列應(yīng)該都是0。
23 int[][] dp = new int[length + 1][k + 1];
24 for (int i = 1; i < dp.length; i++) {
25 Arrays.fill(dp[i], Integer.MAX_VALUE);
26 }
27 //前i個(gè)字符，分割成j個(gè)回文子串
28 for (int i = 1; i <= length; i++) {
29 int len = Math.min(i, k);
30 for (int j = 1; j <= len; j++) {
31 if (j == 1)//字符串的下標(biāo)是從0開始的，所以這里要減1
32 dp[i][j] = palindrome[j - 1][i - 1];
33 else
34 for (int m = j - 1; m < i; m++) {
35 dp[i][j] = Math.min(dp[i][j], dp[m][j - 1] + palindrome[m][i - 1]);
36 }
37 }
38 }
39 return dp[length][k];
40}
因?yàn)閐p[i][j]中i必須大于等于j，所以這里遍歷的時(shí)候可以有兩種方式，如下圖所示
總結(jié)
LeetCode上分隔回文串總共有4題，其中只有一道中等，其他3道都是困難，這里把這4道都講完了，也可以一起看下前面的3道題。
553，動(dòng)態(tài)規(guī)劃解分割回文串 II
570，動(dòng)態(tài)規(guī)劃解回文串分割 IV
聯(lián)系客服
