洛谷题单指南-动态规划3-Zuma

原题链接：https://www.luogu.com.cn/problem/CF607B

题意解读：从一组整数中取连续的回文子串，求最少几次可以取完。

解题思路：

状态表示：设dp[i][j]表示取i~j之间的回文子串所需的最少次数，a[i]表示第i个数

状态转移：

如果a[i] == a[j]，dp[i][j] = dp[i+1][j-1]，因为首尾如果相等，其必然可以和i+1~j-1中最后一个回文子串一起取走。

如果不考虑a[i]和a[j]的关系，采用区间dp的思想，设k取i~j-1之间所有数，有dp[i][j] = min(dp[i][k] + dp[k+1][j])

因此，上面两种情况共同求min即可。

初始化：

由于dp[i][j]依赖dp[i+1][j-1]，所以i~j之间的长度至少从3起，需要对长度是1、2的情况进行初始化

由定义可知dp[i][i] = 1，dp[i][i+1] = 1(当a[i] == a[i+1])或2(当a[i] != a[i+1])

又因为要计算最小值，dp[i][j]最开始要初始化为最大值：memset(dp, 0x3f, sizeof(dp))

结果：dp[1][n]

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 505;
int n;
int a[N];
int dp[N][N]; //dp[i][j]表示取i~j之间的回文子串所需的最少次数

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    memset(dp, 0x3f, sizeof(dp));
    for(int i = 1; i <= n; i++) dp[i][i] = 1;
    for(int i = 1; i < n; i++) dp[i][i+1] = (a[i] == a[i+1] ? 1 : 2);
    for(int len = 3; len <= n; len++)
    {
        for(int i = 1; i + len - 1 <= n; i++)
        {
            int j = i + len - 1;
            if(a[i] == a[j]) dp[i][j] = dp[i+1][j-1];
            for(int k = i; k < j; k++)
            {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]);
            }
        }
    }
    cout << dp[1][n];
    return 0;
}