第一道区间dp题,感觉题意不是很好理解
题意:一次可以转换某一个位置的字符,或是一串连续的字符,举第一个例子zzzzzfzzzzz
1:aaaaaaaaaaa
2: abbbbbbbbba
3: abcccccccba
4: abcdddddcba
5: abcdeeedcba
6: abcdefedcba
于是第一个例子输出6,第二个同理
话不多说,直接贴一波代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<vector>
#include<queue>
#include<map>
#include<iterator>
#include<vector>
#include<set>
#define INF 9999999
typedef long long ll;
const int Max=(<<)+;
using namespace std; int dp[][];//dp[i][j]表示从i~j的刷法
int ans[]; int main()
{
string str1,str2;
int len;
while(cin>>str1>>str2)
{
len=str1.length();
for(int j=;j<len;j++)
{
for(int i=j;i>=;i--)
{
dp[i][j]=dp[i+][j]+;//逐个更新区间i~j内的值
for(int k=i+;k<=j;k++)
{
if(str2[i]==str2[k])//若遇到相同的则需寻找区间的最小值
dp[i][j]=min(dp[i][j],dp[i+][k]+dp[k+][j]);
}
}
} for(int i=;i<len;i++)
ans[i]=dp[][i];//ans[i]表示区间[0,i]需要刷的值
for(int i=;i<len;i++)
{
if(str1[i]==str2[i])//碰到相同的值选择不刷
ans[i]=ans[i-];
else
{
for(int j=;j<i;j++)//寻找最优解
ans[i]=min(ans[i],ans[j]+dp[j+][i]);
}
}
cout<<ans[len-]<<endl;
}
return ;
}