Partitioning by Palindromes UVA - 11584 

動态規劃

判斷回文串采用左右逼近的方法，邏輯簡單也好寫

另外這道題需要多次判斷一個字元串是不是回文串

雖然每次左右邊界不一樣，但是在判斷到一定程度時還是會出現許多重複

例如 判斷1到8 ，先判斷1位置字元是否與8位置字元相同，不同則傳回0

反之遞歸判斷2到7，而2到7我們已經判斷過了，如果我們儲存了這個結果，那麼久可以直接用了

這道題資料規模為1000，是以不那樣儲存也可以

我的寫法就是不儲存的，劉汝佳代碼是更好的做法，

這裡就直接貼劉汝佳代碼了

// UVa11584 Partitioning by Palindromes
// Rujia Liu
// This code is slightly different from the book.
// It uses memoization to judge whether s[i..j] is a palindrome.
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 1000 + 5;
int n, kase, vis[maxn][maxn], p[maxn][maxn], d[maxn];
char s[maxn];

int is_palindrome(int i, int j) {
  if(i >= j) return 1;
  if(s[i] != s[j]) return 0;

  if(vis[i][j] == kase) return p[i][j];
  vis[i][j] = kase;
  p[i][j] = is_palindrome(i+1, j-1);
  return p[i][j];
}

int main() {
  int T;
  scanf("%d", &T);
  memset(vis, 0, sizeof(vis));
  for(kase = 1; kase <= T; kase++) {
    scanf("%s", s+1);
    n = strlen(s+1);
    d[0] = 0;
    for(int i = 1; i <= n; i++) {
      d[i] = i+1;
      for(int j = 0; j < i; j++)
        if(is_palindrome(j+1, i)) d[i] = min(d[i], d[j] + 1);
    }
    printf("%d\n", d[n]);
  }
  return 0;
}