法一:记忆化搜索
要点:记忆剪枝 + 先写下已经固定的状态，再将未知的目标状态 向已知的状态搜索 由已知的状态搜索而来
区别：从后向前推

法二:线性dp 与记忆化相似 区别：从头到尾搜

记搜代码:
#include<bits/stdc++.h>
using namespace std;
int st[45][45][45][45];
int n, m;
int w[400];
int cd[5];

int dfs(int a, int b, int c, int d)
{
    if(st[a][b][c][d])return st[a][b][c][d];//剪枝

//  st[a][b][c][d]++;
    if(a)st[a][b][c][d] = dfs(a - 1, b, c, d);
    if(b)st[a][b][c][d] = max(st[a][b][c][d], dfs(a, b - 1, c, d));
    if(c)st[a][b][c][d] = max(st[a][b][c][d], dfs(a, b, c - 1, d));
    if(d)st[a][b][c][d] = max(st[a][b][c][d], dfs(a, b, c, d - 1));

    st[a][b][c][d] += w[1 + a + 2 * b + 3 * c + 4 * d];
    return st[a][b][c][d]; 
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i = 1;i <= n;i++)cin >> w[i];
    for(int i = 1;i <= m;i++)
    {
        int x;
        cin >> x;
        cd[x]++;
    }

//  memset(st, -1, sizeof st);
    st[0][0][0][0] = w[1];
    int ans = dfs(cd[1], cd[2], cd[3], cd[4]);//从后向前记搜
    cout << ans << endl;
    return 0;
} 

-------------------------------------------------------------dp代码:
#include<bits/stdc++.h>
using namespace std;
int f[45][45][45][45];
int n, m;
int w[400];
int cd[5];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    for(int i = 1;i <= n;i++)cin >> w[i];
    for(int i = 1;i <= m;i++)
    {
        int x;
        cin >> x;
        cd[x]++;
    }

    f[0][0][0][0] = w[1];
    f[1][0][0][0] = w[1] + w[2];
    f[0][1][0][0] = w[1] + w[3];
    f[0][0][1][0] = w[1] + w[4];
    f[0][0][0][1] = w[1] + w[5];
    for(int i = 0;i <= cd[1];i++)
    {
        for(int j = 0;j <= cd[2];j++)
        {
            for(int k = 0;k <= cd[3];k++)
            {
                for(int l = 0;l <= cd[4];l++)
                {
                    if(i)f[i][j][k][l] = max(f[i][j][k][l], f[i - 1][j][k][l]);
                    if(j)f[i][j][k][l] = max(f[i][j][k][l], f[i][j - 1][k][l]);
                    if(k)f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k - 1][l]);
                    if(l)f[i][j][k][l] = max(f[i][j][k][l], f[i][j][k][l - 1]);
                    if(i + j + k + l > 1)f[i][j][k][l] += w[1 + i + 2 * j + 3 * k + 4 * l];
                }
            }
        }
    }
    cout << f[cd[1]][cd[2]][cd[3]][cd[4]] << endl;
    return 0;
}