状态机模型

其实dp问题是在一个有向无环图上递推的过程， 在dag上递推求得答案。 图论问题我们需要建图， 但是dp问题我们不需要真的把图建出来，其实 状态表示，f(i, j)表示的就是图中的一个节点， f(i, j)存的值是从起点到该点的值(最大值、最小值、方案数)。状态转移方程实际上就是描述的是当前点可以由前面的哪些点到达， 按照状态转移方程进行计算，最后根据状态表示求得答案。

简而言之： 状态机能使原来混沌的状态变的更加清晰。

关于状态机如何想出来：

1. 当前节点的状态可以有哪些？
2. 这些状态可以由哪些状态转移过来？

题目一： 大盗阿福

分析：

在背包问题中， 前面一个物品的选择是不会影响后一个物品， 即每个物品的选择都是独立的。

而在状态机模型中， 当前物品的选择是会影响后面物品能不能被选择，由于我们不知道当前物品是不是在最优解的选择中， 所以我们要分别计算出选当前物品和不选当前物品，即在状态表示时加一个维度表示物品是否被选择，最后根据题目的意思画出状态机，写出状态转移方程。

时间复杂度： O ( n ) O(n) O(n), 量级1e5, 1秒之内可以出解。

代码区：

#include
#include

using namespace std;

const int N = 1e5 + 10;

int n;
int w[N];
int f[N][2];

int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        cin >> n;
        
        for(int i = 1; i <= n; i ++) cin >> w[i];
        
        memset(f, -0x3f, sizeof f);
        f[0][0] = 0;
        for(int i = 1; i <= n; i ++)
        {
            f[i][0] = max(f[i - 1][0], f[i - 1][1]);
            f[i][1] = f[i - 1][0] + w[i];
        }
        
        printf("%dn", max(f[n][0], f[n][1]));
    }
    
    return 0;
}

题目2： 股票买卖 IV

分析：

因为求的最大值， 所以初始化成负无穷即可。

我们要确保状态转移方程能够被算出来， 就是确保第一次 f(i - 1, k - 1, 0) 初值为0， 因为是第1次， k等于1。 **f(i , 0, 0)**初始化成0即可， 因为它第一次买入时在每一个点都可能进行。

时间复杂度： O ( n ∗ m ) O(n * m) O(n∗m) 量级1e7, 1秒之内可以出解。

代码区：

#include
#include

using namespace std;

const int N = 1e5 + 10, M = 110;

int n, m;
int w[N];
int f[N][M][2];

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++) cin >> w[i];
    
    memset(f, -0x3f, sizeof f);
    for(int i = 0; i <= n; i ++) f[i][0][0] = 0;
    
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            f[i][j][1] = max(f[i - 1][j][1], f[i - 1][j - 1][0] - w[i]);
            f[i][j][0] = max(f[i - 1][j][1] + w[i], f[i - 1][j][0]);
        }
    }
    
    int res = 0;
    for(int i = 0; i <= m; i ++) res = max(res, f[n][i][0]);
    cout << res << endl;
    
    return 0;
}

题目3： 设计密码

分析：

推荐看这位同学写的 题解

时间复杂度：

代码区：

#include
#include

using namespace std;

typedef long long LL;

const int N = 55, mod = 1e9 + 7;

int n;
char str[N];
int ne[N];
int f[N][N];

int main()
{
    cin >> n >> str + 1;
    int m = strlen(str + 1);
    
    for(int i = 2, j = 0; i <= m; i ++)
    {
        while(j && str[j + 1] != str[i]) j = ne[j];
        if(str[j + 1] == str[i]) j ++;
        ne[i] = j;
    }
    
    f[0][0] = 1;
    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < m; j ++)
        {
            for(char k = 'a'; k <= 'z'; k ++)
            {
                int u = j;
                while(u && str[u + 1] != k) u = ne[u];
                if(str[u + 1] == k) u ++;
                if(u < m) f[i + 1][u] = ((LL)f[i + 1][u] + f[i][j]) % mod;
            }
        }
    }
    
    
    int res = 0;
    for(int i = 0; i < m; i ++) res = ((LL)res + f[n][i]) % mod;
    cout << res << endl;
    
    return 0;
}