SRM 566 Div2 Medium PenguinPals

解法

区間dp
dp[i][j] = [i, j]の最大マッチング

ソースコード

int n;
string c;
int dp[55][55];
int dfs(int l, int r)
{
    if (l >= r)
	return 0;
    else if (dp[l][r] != -1)
	return dp[l][r];

    int res = 0;

    for (int i = l + 1; i <= r; ++i)
	if (c[l] == c[i])
	    chmax(res, 1 + dfs(l + 1, i - 1) + dfs(i + 1, r));

    chmax(res, dfs(l + 1, r));

    return dp[l][r] = res;
}
int PenguinPals::findMaximumMatching(string colors)
{
    c = colors;
    n = colors.size();
    CL(dp, -1);

    return dfs(0, n - 1);
}