今天帶來一個簡單的線性結構上的DP，與上次的照明系統（UVA11400）是同一種類型題，便於大家類比、總結、理解，但難度上降低了。
We say a sequence of characters is a palindrome if it is the same written forwards and backwards. For example, 『racecar』 is a palindrome, but 『fastcar』 is not. A partition of a sequence of characters is a list of one or more disjoint non-empty groups of consecutive characters whose concatenation yields the initial sequence. For example, (『race』, 『car』) is a partition of 『racecar』 into two groups. Given a sequence of characters, we can always create a partition of these characters such that each group in the partition is a palindrome!
正序倒序寫都相同的字符串我們稱之為回文串。例如，『racecar』就是回文的，『fastcar』就不是。對一個字符序列的劃分即：分成一堆（至少一個）非空不相交的連續字符串，使它們連起來就是原來的字符序列。例如，『race』，『car』就是把『racecar』劃分成兩組。給定一個字符串，我們總能找到一種劃分使得每個子串都是回文串！（大不了一個字母算一個子串）
Given this observation it is natural to ask: what is the minimum number of groups needed for a given string such that every group is a palindrome?For example:
『racecar』 is already a palindrome, therefore it can be partitioned into one group.
『fastcar』 does not contain any non-trivial palindromes, so it must be partitioned as (『f』, 『a』, 『s』, 『t』, 『c』, 『a』, 『r』).
『aaadbccb』 can be partitioned as (『aaa』, 『d』, 『bccb』).
求：使得每個子串都是回文串的最小劃分組數。
例如，『racecar』本身就是個回文串所以它的答案是1組；『fastcar』不含回文子串，只能一個字母一個字母地分，答案為7組；『aaadbccb』最優可以分成『aaa』，『d』，『bccb』3組。
InputInput begins with the number n of test cases. Each test case consists of a single line of between 1 and 1000 lowercase letters, with no whitespace within..
最先輸入測試組數n。每組給出一個長度1~1000的小寫字母串，中間沒有空格。
OutputFor each test case, output a line containing the minimum number of groups required to partition the input into groups of palindromes.
對於每組測試，輸出可劃分的最少組數。
Sample Input3
racecar
fastcar
aaadbccb
Sample Output1
7
3
思路：
假如我遍歷一遍字符串 ----> 強如『fastcar』的話只能一個字母一個字母地苦逼+1，那麼有回文子串時，差異是如何產生的呢？ ----> 就說racecar吧。走到race的時候還是+1模式，再走一步到c的時候發現跟前面的ce能湊個cec ----> 我們用dp數組表示結果，dp[racec]本來等於dp[race]+1,由於找到了回文子串cec，所以變成了min（ dp[race]+1, dp[ra]+1 ） ----> 由於我們不知道當前字母最早可以伸展到哪裡去跟別人結合為回文子串，所以可以暴力掃一遍前面的 ----> 至於回文串，一邊掃一遍判斷也可以，預處理也可以，關鍵是複雜度。預處理可以枚舉回文串中心然後向左右伸展得到（j，i）是不是回文串，可以以n的複雜度求解，這樣dp的過程也是n。一邊dp一邊判斷大概是n的複雜度，我不知道怎麼就過了我複雜度算錯了？……
最開始瞎寫的代碼1：20ms
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;int T;int dp[1001];char str[1001];boolispalindrome(int start, int end){for (int i = start; i < (start+end+1)/2; i++)if (str[i] != str[start+end-i])returnfalse;returntrue;}intmain(){scanf("%d", &T);while (T--) {scanf("%s", str+1);int len = strlen(str+1);for (int i = 1; i <= len; i++) { dp[i] = dp[i-1] + 1;for (int j = 1; j <= i-1; j++)if (ispalindrome(j, i))//[j,i]是不是回文 dp[i] = min(dp[i], dp[j-1] + 1); }printf("%d\n", dp[len]); }}
按照上面瞎改的代碼2：20ms
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;int T;int dp[1001];char str[1001];bool ispalindrome[1001][1001];intmain(){scanf("%d", &T);while (T--) {scanf("%s", str+1);int len = strlen(str+1);memset(ispalindrome, false, sizeof(ispalindrome));memset(dp, 0x3f, sizeof(dp));//預處理for (int i = 1; i <= len; i++) {for (int l = i, r = i; str[l] == str[r] && l >= 1 && r <= len; l--, r++) ispalindrome[l][r] = true;for (int l = i, r = i+1; str[l] == str[r] && l >= 1 && r <= len; l--, r++) ispalindrome[l][r] = true; }//dp dp[0] = 0;for (int i = 1; i <= len; i++)for (int j = 1; j <= i; j++)if (ispalindrome[j][i])//[j,i]是不是回文 dp[i] = min(dp[i], dp[j-1] + 1);printf("%d\n", dp[len]); }}
溫馨提示
如果你喜歡本文，請分享到朋友圈，想要獲得我。
ACM算法日常
點讚的時候，請寵溺一點