一、解题基本步骤

状态机问题解题的第一步是画出正确的转移模型，其通常用一个状态机的图来进行表示。

可以从一道简单的题来开始认识状态机模型的画法。大盗阿福  https://www.acwing.com/problem/content/1051/

第二步是根据转移模型，写状态转移方程，还要注意变量的初始化问题，通常将起点设置为0,1等，将不可以作为转移源头的点设置为负无穷等。

二、一些经典变体

1.股票交易IV

https://www.acwing.com/problem/content/description/1059/

因为是状态机，所以第三维要有0和1的状态，又因为是二维，所以要有i和j

对于每次交易，以交易完成或进行中标定状态，注意这个一定要规定好，否则状态转移方程就会出错。比如这道题，一次交易只有真正卖掉股票才是交易结束，所以f[i][j][0]表示手中没有股票，且进行完了j次交易，而f[i][j][1]表示手中有股票，这时第j次交易必然还正在进行。所以就出现了f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+w[i]);所以max函数的第二个参数是f[i-1][j][1]+w[i]，这里是j而不是j-1,而f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-w[i]);这里就是j-1

2.设计密码

https://www.acwing.com/problem/content/1054/

状态机结合字符串算法

3.洛谷P1353 [USACO08JAN]Running S

https://www.luogu.com.cn/problem/P1353

难点在于状态机模型的绘制

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cstdio>
 5 #define ll long long
 6 using namespace std;
 7 const int N=10050;
 8 const int M=1050;
 9 ll f[N][M][2];
10 int n,m;                                                //一定要首先规定清楚是表示这一分钟刚开始时的跑步总路程还是这一分钟结束时的，本代码表示结束时的
11 int w[N];
12 int main(){
13     
14     cin>>n>>m;
15     for(int i=1;i<=n;i++) scanf("%d",&w[i]);
16     //f[1][0][0]=0;
17     f[0][0][1]=-1;
18     for(int i=1;i<=n;i++)
19         for(int j=0;j<=m;j++){
20             f[i][j][0]=max(f[i-1][j][0],max(f[i-1][j+1][0],f[i-1][j+1][1]));//特殊的是，休息不一定从运动转移过来,还可能由初始状态转移过来，或者从其它休息状态转移过来
21             
22             if(j) f[i][j][1]=max(f[i-1][0][0],f[i-1][j-1][1])+w[i];
23             //else f[i][j][1]=f[i-1][0][0]+w[i];                   //这是不合法的状态，不可能运动后疲劳值还是0
24         
25             //f[i][0][0]=max(f[i][0][0],max(f[i-j][j][0],f[i-j][0][0]));
26         }
27     
28     cout<<f[n][0][0];
29     
30     
31     return 0;
32     
33 }

4.修复DNA

https://www.acwing.com/problem/content/1055/

AC自动机