本文主要是介绍A5(用状态机模型解决字符串问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
明明状态2是可以由状态4转移过来的（也就是说AAA5再遇到5的时候会变成AAA55，此时不得不转移这个非法状态了，那么如果改5为A的话，就会回到状态4，如果随便改一个A为5的话，就会回到状态2（AA555），可是为什么我加入这个状态2的转移入口的时候反而错了呢？！奇怪了奇怪了。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string s;
int t,n;
int dp[1000][5];
int minn(int a,int b,int c){return min(a, min(b,c));
}
int main(){cin>>t;while(t--){memset(dp,0x3f,sizeof dp);cin>>s;n=s.length();//cout<<"n="<<n<<endl;if(n<5){cout<<"0"<<endl;continue;}//入口for(int i=1;i<=4;i++)dp[0][i]=0;if(s[0]=='A')dp[0][0]=1;else dp[0][0]=0;for(int i=1;i<n;i++){if(s[i]=='A'){dp[i][0]=dp[i-1][0]+1;dp[i][1]=min(dp[i-1][1]+1,dp[i-1][0]);dp[i][2]=min(dp[i-1][2]+1,dp[i-1][1]);dp[i][3]=dp[i-1][3];//这2个状态是为了不脱节状态内的转移，上面3个是状态间的转移dp[i][4]=dp[i-1][4];}if(s[i]=='5'){dp[i][0]=dp[i-1][0];dp[i][1]=dp[i-1][1];dp[i][2]=dp[i-1][2];//这三个状态是为了不脱节状态内的转移，下面两个是状态间的转移//dp[i][2]=min(dp[i-1][2],dp[i-1][4]+1);dp[i][3]=min(dp[i-1][3]+1,dp[i-1][2]);dp[i][4]=min(dp[i-1][4]+1,dp[i-1][3]);}//cout<<"dp["<<i<<"][0 1 2]="<<dp[i][0]<<"--"<<dp[i][1]<<"--"<<dp[i][2]<<endl;//cout<<"dp["<<i<<"][3 4]="<<dp[i][3]<<"--"<<dp[i][4]<<endl;}//出口int min1=min(dp[n-1][4],dp[n-1][1]);int min2=min(dp[n-1][2],dp[n-1][3]);cout<<min(min1,min2)<<endl;}
}
上面是加注释版的代码
下面是删减版代码（就是想看看code能短到什么长度hhh
#include <bits/stdc++.h>
using namespace std;
string s;
int t,n;
int dp[1000][5];
int main(){cin>>t;while(t--){memset(dp,0x3f,sizeof dp);cin>>s;n=s.length();for(int i=1;i<=4;i++)dp[0][i]=0;if(s[0]=='A')dp[0][0]=1;else dp[0][0]=0;for(int i=1;i<n;i++){if(s[i]=='A'){dp[i][0]=dp[i-1][0]+1;dp[i][1]=min(dp[i-1][1]+1,dp[i-1][0]);dp[i][2]=min(dp[i-1][2]+1,dp[i-1][1]);dp[i][3]=dp[i-1][3];dp[i][4]=dp[i-1][4];}if(s[i]=='5'){dp[i][0]=dp[i-1][0];dp[i][1]=dp[i-1][1];dp[i][2]=dp[i-1][2];dp[i][3]=min(dp[i-1][3]+1,dp[i-1][2]);dp[i][4]=min(dp[i-1][4]+1,dp[i-1][3]);}}int min1=min(dp[n-1][4],dp[n-1][1]);int min2=min(dp[n-1][2],dp[n-1][3]);cout<<min(min1,min2)<<endl;}
}
这篇关于A5(用状态机模型解决字符串问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
