DP

背包

01背包

  int n, v;
    scanf("%d %d", &n, &v);
    for(int i = 1; i <= n; i++)
        scanf("%d %d", &V[i], &W[i]);

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= v; j++)
        {
            f[i][j] = f[i - 1][j];
            if(j >= V[i])
                f[i][j] = max(f[i][j], f[i - 1][j - V[i]] + W[i]);
        }
    }
    printf("%d", f[n][v]);

一维优化

int n, v;
    scanf("%d %d", &n, &v);
    for(int i = 1; i <= n; i++)
        scanf("%d %d", &V[i], &W[i]);

    for(int i = 1; i <= n; i++)
    {
        for(int j = v; j >= V[i]; j--)
            f[j] = max(f[j], f[j - V[i]] + W[i]);
    }
    printf("%d", f[v]);
    return 0;
————————————————

完全背包 物品的数量是无限的

  int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d %d", &v[i], &w[i]);

    for(int i = 1; i <= n; i++)
    {
        for(int j = v[i]; j <= m; j++)
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }


    printf("%d", f[m]);
————————————————

多重背包 多重背包既不是最多一个，也不是无限个，是有给定数量的。

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d %d %d", &v[i], &w[i], &s[i]);

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            for(int k = 0; k <= s[i] && k * v[i] <= j; k++)
            {
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
            }
        }
    }

    printf("%d", f[n][m]);
————————————————

二进制优化多重背包

int n, m;
int v[N], w[N]; //逐一枚举最大是N*logS
int f[M]; // 体积<M

int main()
{
    cin >> n >> m;
    int cnt = 0; //分组的组别
    for(int i = 1;i <= n;i ++)
    {
        int a,b,s;
        cin >> a >> b >> s;
        int k = 1; // 组别里面的个数
        while(k<=s)
        {
            cnt ++ ; //组别先增加
            v[cnt] = a * k ; //整体体积
            w[cnt] = b * k; // 整体价值
            s -= k; // s要减小
            k *= 2; // 组别里的个数增加
        }
        //剩余的一组
        if(s>0)
        {
            cnt ++ ;
            v[cnt] = a*s; 
            w[cnt] = b*s;
        }
    }

    n = cnt ; //枚举次数正式由个数变成组别数

    //01背包一维优化
    for(int i = 1;i <= n ;i ++)
        for(int j = m ;j >= v[i];j --)
            f[j] = max(f[j],f[j-v[i]] + w[i]);

    cout << f[m] << endl;

记忆化搜索

记忆化搜索+动态规划

int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int a[MAXN][MAXN],f[MAXN][MAXN];
int dfs(int x,int y)
{
    if(f[x][y]!=-1)
        return f[x][y];
    f[x][y]=1;//记得赋值为1
for(int i=0;i<=3;i++)
{
        int dx=x+dir[i][0],dy=y+dir[i][1];
        if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&a[dx][dy]<a[x][y])
            f[x][y]=max(f[x][y],dfs(dx,dy)+1);
    }
    return f[x][y];
}

最长公共子序列

 for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            f[i][j]=max(f[i-1][j],f[i][j-1]);
            if(a[i]==b[j])
                f[i][j]=max(f[i][j],f[i-1][j-1]+1);
        }