[Quy hoạch động] [SPOJ] COUNTPL

Đề bài
Hướng làm
Bước 1:
Tham khảo Nguyễn Hoành Tiến, đã sửa lại cho đúng
Dùng mảng F[i, j] có ý nghĩa: F[i, j] = true/false nếu đoạn gồm các kí tự từ i đến j của S có/không là palindrome.
Ta có công thức là:
F[i, i] = True
F[i, j] = (F[i+1, j-1] or (j-i=1)) ( nếu S_i = S_j )
F[i, j] = False; ( nếu S_i <> S_j )
Bước 2:
Gọi dp[i] là kết quả nếu chỉ xét xâu s[1..i].
Ta có dp[i]=dp[j-1]+1 với dp[j-1] nhỏ nhất và thỏa mãn j<=i và f[j,i] (giống bài NKREZ)
Code