动态规划学习笔记（待更新...)

动态规划

（无模板）

背包问题

1. 01 01 01背包：每件物品最多用一次

2.完全背包：每件物品有无限个

3.多重背包：每种物品个数不一样，有限制（可优化）

4.分组背包： n n n组物品，每组物品最多只能选一种物品

例题： 01 01 01背包

优化前：

#include 
#include 
using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int f[N][N];//状态集合，初始值都为0

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> v[i] >> w[i];
    for(int i=1;i<=n;i++)//*从第1件物品开始枚举，因为第0件已经为0
        for(int j=0;j<=m;j++){/从0开始枚举体积
            f[i][j]=f[i-1][j];//体积为j时不选第i件，等价于体积为j,还没选第i件物品
            if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);//*如果目前体积大于等于目前正在选的第i件物品的体积，将选与不选这一件物品获得的价值作比较取最大值
        }
    cout << f[n][m] << endl;
    return 0;
}

优化后：

#include 
#include 
using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int f[N];//去掉第一维

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> v[i] >> w[i];
        // for(int i=1;i<=n;i++)
    //     for(int j=0;j<=m;j++){
    //         f[i][j]=f[i-1][j];去掉第一维->f[j]=f[j]恒等式直接删掉
    //         if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);将for循环条件优化为(int j=v[i];j<=m;j++) 后续则变为f[j]=max(f[j],f[j-v[i]]+w[i]); 但此时我们使用的数据不是v[i-1]的数据了，因为j-v[i]一定是小于j,所以f[j-v[i]]会较早更新到，后续就会使用到这一轮刚跟新了的数据，也就是v[i]这一层的数据，但将j从m到v[i]递减枚举就会保证使用的数据全部为v[i-1]层的
    //     }
    for(int i=1;i<=n;i++)
        for(int j=m;j>=v[i];j--)//*从m到v[i]开始枚举保证使用的是v[i-1]的数据
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    cout << f[m] << endl;
    return 0;
}

对于优化方式的一些解释：

采用滚动数组，在下一次更新前，使用的数据是上一次存在的（今天才悟到滚动数组的含义！）

首先我们可将for循环条件优化为 ( i n t   j = v [ i ] ; j ≤ m ; j + + ) (int\ j=v[i];j\le m;j++) (int j=v[i];j≤m;j++) 后续则变为 f [ j ] = m a x ( f [ j ] , f [ j − v [ i ] ] + w [ i ] ) ; f[j]=max(f[j],f[j-v[i]]+w[i]); f[j]=max(f[j],f[j−v[i]]+w[i]); 但此时我们使用的数据不是 v [ i − 1 ] v[i-1] v[i−1]的数据了，因为 j − v [ i ] j-v[i] j−v[i]一定是小于 j j j,所以 f [ j − v [ i ] ] f[j-v[i]] f[j−v[i]]会较早更新到，后续就会使用到这一轮刚跟新了的数据，也就是 v [ i ] v[i] v[i]这一层的数据，但将 j j j从 m m m到 v [ i ] v[i] v[i]递减枚举就会保证使用的数据全部为 v [ i − 1 ] v[i-1] v[i−1]层的,也就是全都是上一层保存的，未在这一层更新过的。（终于搞懂了）

例题：完全背包问题

优化过程：

#include 
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int f[N][N];
int f1[N];

signed main(){
    cin  >> n >> m;
    for(int i=1;i<=n;i++) cin >> v[i] >> w[i];
    // for(int i=0;i<=n;i++)    //* 优化前 
    //     for(int j=0;j<=m;j++)
    //         for(int k=0;k*v[i]<=j;k++)  f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);

    // cout << f[n][m] << endl;    
    //* 优化后 变为二维 
    // for(int i=1;i<=n;i++)
    //     for(int j=0;j<=m;j++){
    //         f[i][j]=f[i-1][j];
    //         if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]); //!从i转移过来 因为在这一层上要选若干个，用这一层更新过的数据
    //     }
    // cout << f[n][m] << endl;
    //* 优化为一维
    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=m;j++)//*使用第i层数据，从小到大枚举
            f1[j]=max(f1[j],f1[j-v[i]]+w[i]);
    cout << f1[m] << endl;
    return 0;
}

优化版本：

#include 
#include 
using namespace std;

const int N = 1010;
int n,m;
int f[N],v[N],w[N];

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> 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]);
        }
            
    cout << f[m] << endl;
    return 0;
}

优化原理：

在同一层上，依次减掉更多的 v [ i ] v[i] v[i],下一次减 v [ i ] v[i] v[i]可以在上一次的基础上进行 *** 作，所以用的是同一层的数据。

例题：多重背包问题

状态转移方程： f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j − v [ i ] ∗ k ] + w [ i ] ∗ k )   ( 0 ≤ k ≤ s [ i ] ) f[i][j]=max(f[i-1][j-v[i]*k]+w[i]*k)\ (0\le k\le s[i]) f[i][j]=max(f[i−1][j−v[i]∗k]+w[i]∗k) (0≤k≤s[i])

#include 
#include 
using namespace std;

const int N = 110;
int n,m;
int v[N],w[N],s[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> v[i] >> w[i] >> s[i];
    for(int i=1;i<=n;i++)
        for(int j=0;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]);
            }
    cout << f[n][m] << endl;
    return 0;
}

优化后：

（二进制优化）

#include 
using namespace std;

const int N =25000,M=2010;
int n,m; 
int v[N],w[N];
int f[N];

signed main(){
    cin >> n >> m;
    int cnt=0;  
    //for(int i=1;i<=n;i++) cin >> v[i] >> w[i] ;
    //*      优化前
    // for(int i=1;i<=n;i++)
    //     for(int j=0;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]]+w[i]*k);
    //         }    
    // cout << f[n][m] << endl;
    //* 优化后(二进制优化)  将s[]拆分 再对分完的组进行01背包问题求解
    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;//第cnt组的体积
            w[cnt]=b*k;//价值
            s-=k;//*剩余未打包的数量
            k<<=1;//下一组的数量要加倍
        }
        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;
    return 0;
}

将每一种物品都按照上述方法拆分后可以保证有选法能拼凑出打包前所有选法（也就是选几个的问题），由一个一个选优化为一坨一坨地选，将所有种类的物品都做这种处理，最终混在一起，记录一共有多少坨，对这些坨做01背包。

（原来每件物品有 n n n件，分组后就有 l o g 2 n log_2n log2​n组，对这些组进行枚举，从而使时间复杂度降为 l o g log log级别。）

例题：分组背包问题

#include 
using namespace std;

const int N = 1010;

int n,m;
int s[N],v[N][N],w[N][N],f[N];

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)//*组数
    {
        cin >> s[i];//每组的数量
        for(int j=1;j<=s[i];j++)
        {
            cin >> v[i][j] >> w[i][j];//*第i组内第j个物品属性
        }
    }
    for(int i=1;i<=n;i++)//*每组
        for(int j=m;j>=0;j--)//*枚举容量从大到小，用i-1层防止覆盖数据
            for(int k=1;k<=s[i];k++)//*枚举组内第k个物品
            {
                if(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);//*如果当前容量大于当前物品容量才有意义，取最大
            }
    cout << f[m] << endl;
    return 0;
}

线性 D P DP DP

例题：数字三角形

#include 
using namespace std;

const int N = 510, INF = 1e9;
int n;
int a[N][N],f[N][N];//存放三角形及每个位置的状态

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin >> a[i][j];
    for(int i=0;i<=n;i++)//*注意初始化的范围
        for(int j=0;j<=i+1;j++)//*边界及边界之外也要初始化，因为会用到
            f[i][j]=-INF;
    f[1][1]=a[1][1];//顶点的最大值就是自身
    for(int i=2;i<=n;i++)//从第二行开始枚举
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);//*两个方向过来的上一个状态的和加现在这点的数值取最大值
    int res=-INF;
    for(int i=1;i<=n;i++) res=max(f[n][i],res);//*找出最后一行的最大值为答案
    cout << res << endl;
    return 0;
}

例题：最长上升子序列

#include 

using namespace std;

const int N = 1010;
int n;
int a[N],f[N];//*存数值和状态

int main()
{
    cin >> n ;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++)//*找以i为结尾的最长上升子序列
    {
        f[i]=1;//*初始最长为自身长度为1
        for(int j=1;j<i;j++){
            if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[i]);//枚举每个结尾找最长的
    cout << res << endl;
    return 0;
}

第二次再写这道题目，加深了理解：

枚举 j j j那个循环中，如果 a [ j ] < a [ i ] a[j]a[j]<a[i],则比较此时 j j j位置的状态（即以 j j j结尾的最长上升子序列的长度+1（加的这个1是加的 a [ i ] a[i] a[i]位置的一个数），也算是一个集合）与 i i i位置的状态取最大值并更新，以此类推…

就是用前面推完的状态更新后面的状态，所以确定好最初的状态也很关键，比如这里的，将以每一个数结尾的初始长度都初始为1，不管有没有别的数，他自己肯定算一个呀！

再写一遍：（(ˉ▽ˉ；)…） 还是要注意初始状态的呀，或者说已知状态，比如f[1]=1,通过第一层for循环中的i=1来实现。

输出路径：没搞明白

#include 

using namespace std;

const int N = 1010;
int n;
int a[N],f[N],g[N];

int main()
{
    cin >> n ;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        g[i]=0;
        for(int j=1;j<i;j++){
            if(a[j]<a[i]) 
                if(f[i]<f[j]+1){
                    f[i]=f[j]+1;
                    g[i]=j;//记录路径
                }
        }
    }
    //int res=0;
    int k=1;//最优解下标
    for(int i=1;i<=n;i++)
        if(f[k]<f[i]) k=i;
    for(int i=1;i<=n;i++) res=max(res,f[i]);
    cout << res << endl;
    return 0;
}

例题：最长公共子序列

#include 
using namespace std;

const int N = 1010;

int n,m;
char a[N],b[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    // scanf("%s",a+1);
    // scanf("%s",b+1);
    scanf("%s%s",a+1,b+1); //*需要用到i-1和j-1，从1开始存
    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);
        }
    cout << f[n][m] << endl;//*最后一个一定是最长的，从前往后推的
    return 0;
}

讲的太好了！

/*如果两个都不相等，等价于 f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] f[i][j]=f[i-1][j-1] f[i][j]=f[i−1][j−1]，而 f [ i ] [ j ] = m a x ( f [ i − 1 ] [ j ] , f [ i ] [ j − 1 ] ) f[i][j]=max(f[i-1][j],f[i][j-1]) f[i][j]=max(f[i−1][j],f[i][j−1])*/

啥也没说，思路有点混了。。。

区间 D P DP DP

例题：石子合并

#include 
using namespace std;

const int N = 310;
int n;
int s[N],f[N][N];

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++) cin >> s[i];
    for(int i=1;i<=n;i++) s[i]+=s[i-1];//求前缀和
    for(int len=2;len<=n;len++)
        for(int i=1;i+len-1<=n;i++)
        {
            int l=i,r=i+len-1;  //区间范围
            f[l][r]=1e9;        //*初始化后续做比较取最小
            for(int k=l;k<r;k++)
                f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
        }
    cout << f[1][n] << endl;
    return 0;
}

坑🕳： f o r ( i n t   l e n = 2 ; l e n ≤ n ; l e n + + ) for(int\ len=2;len\le n;len++) for(int len=2;len≤n;len++) 竟然长度是从 2 2 2枚举到 n ? ? n?? n??

不能理解。。。到 n − 1 n-1 n−1输出一直为 0 0 0…

好像知道了，下一步循环要用到 l e n len len, l e n len len到 n n n后面求右边界才能到达 n n n的位置。