母题
令 \(f[i,j]\) 表示区间内的信息。
考虑转移就是 \(f[i,j]=f[i,k]+f[k+1][j]+merge([i,k],[k+1,j])\)，merge 可以用前缀和。
1
考虑若两端点相等，那么可以连着，即 \(a_i=a_j,f[i][j]\leftarrow f[i+1][j-1]\)，还有一种情况类似于上面的直接劈开。
2
比较麻烦，类似于母题，但是需要加一些特殊处理，而且边界。
3
转移有很多。
首先如果 \(s[i]==s[j]\)，你可以考虑 \(f[i][j]\leftarrow f[i+1][j],f[i][j-1],f[i+1][j-1]+1\)（前两个必选一个，最后一个可选可无）。
其次就是类似于母题的转移。
对于上面那个，可以理解为覆盖的顺序是可以灵活调动的，而第三个并不符合这一点。
总结
区间 DP，状态必须有区间，基本的题都有边界的处理（如1,3中相等的情况，2中一匹、两匹，以及1，2中合并的处理），当然必不可少的是区间的合并。