Studying Father's luogu blog

Studying Father's luogu blog

从零至灵,由壹达意

题解 CF1132F 【Clear the String】

posted on 2019-06-14 23:37:25 | under 题解 |

这是一道非常基础的区间DP题。与其他几篇题解稍有不同,这篇题解的DP采用了记忆化搜索实现。

我们设 $ f_{l,r} $ 代表删除 $ l $ 到 $ r $ 之间的所有字符的最小花费。

那么有两种决策:

  1. 单独删掉开头的字符,则 $ f_{l,r} = f_{l+1,r} + 1 $ 。
  2. 在串中找到一个与开头字符相同的位置一块删,我们枚举中间位置 $ k $ ,则有 $ f_{l,r} = \min (f_{l+1,k-1},f_{k,r}) $ 。

本题采用记忆化搜索的优点在于,我们无需确定递推的转移顺序,只需按照自然的 dfs 顺序搜索即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[505];
int f[505][505];
int dfs(int l,int r)
{
 if(f[l][r]!=-1)return f[l][r];
 if(l==r)return f[l][r]=1;
 if(l>r)return f[l][r]=0;
 f[l][r]=1+dfs(l+1,r);
 for(int i=l+1;i<=r;i++)
  if(s[l]==s[i])f[l][r]=min(f[l][r],dfs(l+1,i-1)+dfs(i,r));
 return f[l][r];
}
int main()
{
 int n;
 memset(f,-1,sizeof(f));
 scanf("%d",&n);
 scanf("%s",s);
 printf("%d\n",dfs(0,n-1));
 return 0;
}