Zuma（区间DP）

Coding_Guy · 2021-02-09 14:15:51 · 个人记录

给一个数字序列，每次可以操作一次，选其中一段回文子序列删掉，剩下序列左右合并，问最少操作多少次可以全部删掉。

令f[l][r]表示将序列[l,r]的这段数字序列删掉需要的最少操作次数。

如果要把a[r+1]放到f[l][r]里，要删掉a[r+1]的话，只需要枚举区间[l,r]里面和a[r+1]相同的地方，假设是k，如果k<r，那现在f[l][r+1]就等于f[l][k-1]+f[k+1][r]。

如果k=r，那现在f[l][r+1]=f[l][r-1];

为了保证子问题在之前都求解过了，枚举区间长度len，再枚举起点即可。