一、题目

二、题解：

1、题目解析：

1）刚刚开始阅读到题目，我们发现并没有什么思路，因此我们可以尝试来模拟一下样例的情况

2）通过观察我们发现

• $n=2:$可以拆分成$1+1$来解决问题
• $n=3:$可以拆分成$1+2$，$2+1$来解决问题
• 看出：大区间的次数由小区间合并而来---->$区间DP$。
• 因此，我们考虑可以使用区间DP来实现功能

3）状态转移方程

2、区间DP实现

1）字符串预处理

• 将字符串下标至为从1开始
• 初始化$DP$数组，因为本身->本身只需要涂一次，因此：dp[i][i]=1

  string s;cin>>s; 
  s=' '+s; //字符串数组下标映射到1
  int n=s.size()-1; //存储字符串长度

  memset(dp,0x3f,sizeof(dp));

  //区间DP模板,
  for(int i=1;i<=n;i++) dp[i][i]=1; //dp数组初始化

2）区间DP模板

2）通过以上分析，我们可以发现只需要修改k分割点的部分即可实现

	 //当首尾相等时，说明可以不用考虑首/尾
	  if(s[i]==s[j]) dp[i][j]=min(dp[i+1][j],dp[i][j-1]);
      else //不相等时，将其拆分
      {
        for(int k=i;k<j;k++) //枚举分割点,求每个拆分区间的最小值
        {     
          dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);
        }
      }

三、完整代码实现：

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

const int N=57;
int dp[N][N]; //表示到了区间[i->j]时的最少涂色次数


void solve()
{
  string s;cin>>s; 
  s=' '+s; //字符串数组下标映射到1
  int n=s.size()-1; //存储字符串长度

  memset(dp,0x3f,sizeof(dp));

  //区间DP模板,
  for(int i=1;i<=n;i++) dp[i][i]=1; //dp数组初始化
  for(int len=2;len<=n;len++) //枚举区间长度
  {
    for(int i=1;i+len-1<=n;i++) //枚举区间左端点
    {
      int j=i+len-1;  //枚举区间右端点

      if(s[i]==s[j]) dp[i][j]=min(dp[i+1][j],dp[i][j-1]);//当首尾相等时，说明可以不用考虑首/尾
      else //不相等时，将其拆分
      {
        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]<<'\n';
}

int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int _=1;
  while(_--) solve();
  return 0;
}