动态规划学习-基础篇2

动态规划基础学习第二篇咯，这次是补一下基础模型（中间多了很多事，最后几道耽搁了好久）

参考：

AcWing算法基础课

会把AcWing算法基础课动态规划部分所有的题目过一遍，有的题目上一篇讲过了这里就不会再提及了，可以去这里看

背包问题

这里先只讲课程里面的东西，后面有时间看看把背包九讲全复习一遍

01背包问题

看这里动态规划学习-基础篇1

完全背包问题

看这里动态规划学习-基础篇1

多重背包问题 I

题目链接

老规矩闫式DP分析法直接上！

duochong-1.png

我就不再像上一篇一样每个都细讲一遍了，相信大家都能看懂（尤其是某人 U•ェ•*U

其实多重背包可以思考为一个有很多相同物品的01背包，也可以看成有数量限制的完全背包，比较简单，直接开始coding

朴素版本

#include<iostream>

using namespace std;

const int N = 110;

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

int main(){
    int n,m;
    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=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-v[i]*k]+k*w[i]);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

也可以直接读一个处理一个数据，少开几个数组

#include<iostream>

using namespace std;

const int N = 110;

int f[N][N];

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

空间优化

压缩为一维数组即可

#include<iostream>

using namespace std;

const int N = 110;

int f[N];

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

多重背包问题 II

题目链接

这道题相对于上一道主要是对数据进行了加强，需要引入二进制表示法来进行优化，举个简单的例子，以前要表示1~200需要枚举1,2,3,...,199,200这样200个状态，但是如果用二进制表示法只需要使用$$2^0,2^1,2^2,2^3,2^4,2^5,2^6,73$$这8个数就可以表示出1~200中的所有的数了（前面的数可以表示出1~127，所以最后补一个73就可以表示出73~200的数了，那么就可以表示出1~200的所有数了），这就是二进制优化。

二进制优化版

二进制优化完其实就是直接解一个01背包问题了

#include<iostream>

using namespace std;

const int N = 25000; //N>1000*log(20000)

int v[N],w[N];
int f[N];

int main(){
    int n,m;
    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;
            k *= 2;
        }
        if(s>0){
            cnt++;
            v[cnt] = a*s;
            w[cnt] = b*s;
        }
    }
    for(int i=1;i<=cnt;i++){ //注意这里拆分出的物品种数变成了cnt种
        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;
}

分组背包问题

题目链接

fenzu.png

分组背包其实就是每组最多只能选一个，多一重循环就行了

朴素版本

这里主要说一下为什么要固定体积再选物品，而不是固定一个物品去遍历体积，是因为先固定物品的话算完这一个物品后再去算同组的下一个问题会使用上一个物品更新后的值，就会导致结果错误，具体的可以看这里的讨论区，很多好的解释，这里截取一个放在下面。

假设对第i组里的物品k，把所有体积遍历了一次，然后选择了这件物品，这个时候f[i][j]已经包含了第i组中一个物品，也就是k；接下来还是这一组，第k+1个物品，又枚举所有体积，并且你也选择了这一个物品，即f[i][j]=max(f[i-1][j],f[i-1][j-v[i][k+1]]+w[i][k+1])中后者更大，更新之后f变成了后者
这就意味着在第i组中同时选择了k和k+1两个物品
而如果固定体积，遍历物品，就不会有这个问题，因为每次遍历都只能选中一件物品；
这本质上还是在优化成一维数组之后数组的更新过程中需要注意的问题，就像y总说的要保证等价

然后写一下代码

#include<iostream>

using namespace std;

const int N = 110;

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

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

或者也可以这么写，可能更好理解一点

#include<iostream>

using namespace std;

const int N = 110;

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

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

空间优化

#include<iostream>

using namespace std;

const int N = 110;

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

int main(){
    int n,m;
    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];
        }
    }
    
    for(int i=1;i<=n;i++){
        for(int j=m;j>=0;j--){
            for(int k=1;k<=s[i];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;
}

线性DP

数字三角形

题目链接

linear-1.png

这里主要有一个点要讲，就是状态的递推要从下往上，因为从上往下的话，对于边界的点，其左下或者右下可以没点，但从下往上就可以免除这种边界问题

朴素代码

#include<iostream>

using namespace std;

const int N = 510;

int f[N][N],w[N][N];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>w[i][j];
        }
    }
    for(int j=1;j<=n;j++) f[n][j] = w[n][j]; //最后一行的结果只能来自自身
    for(int i=n;i>=1;i--){
        for(int j=1;j<=i;j++){
            f[i][j] = max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j]);
        }
    }
    cout<<f[1][1]<<endl;
    return 0;
}

优化版本

#include<iostream>

using namespace std;

const int N = 510;

int f[N][N];

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

最长上升子序列

题目链接

linear-2.png

代码

注意下是严格单调递增就好

#include<iostream>

using namespace std;

const int N = 1010;

int f[N],a[N];

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

最长上升子序列 II

题目链接

数据加强了，这里使用的方法更像是一种贪心的思想。

对于相同长度的子序列来说，如果现在要选的这个数比该长度子序列的最大的末尾数还大的话，那它就一定可以接在这个长度的所有子序列的后面，所以每个长度只需要记录该长度下最大的末尾数即可。

代码

找最大的末尾数的时候可以用二分

#include<iostream>

using namespace std;

const int N = 100100;

int a[N],q[N];

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    q[0] = -2e9; //哨兵，保证找到的子序列不会长度为0
    int len=0;
    for(int i=0;i<n;i++){
        int l=0,r=len;
        while(l<r){
            int mid = l+r+1>>1;
            if(q[mid]<a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len,r+1);
        q[r+1] = a[i];
    }
    cout<<len<<endl;
    return 0;
}

最长公共子序列

看这里动态规划学习-基础篇1

最短编辑距离

题目链接

linear-3.png

这里最后一步操作只需要考虑最后一个字符是因为我们前面已经将状态不重不漏的划分成了删增改三个子问题（其实说4个子问题更恰当，因为改有两种情况，最后一个字符相等就不操作，不想等就改这两种），所以在考虑最后一步操作的时候前面的字符全部都是操作好的，如果不是，那么就可以将前一个状态继续划分为子问题，直至有一个长度为1或有一个为0，因此逻辑是闭环的。

代码

有i-1这种减法操作的时候可以考虑下标从1开始，这样可以省略对边界值的判断

#include <iostream>

using namespace std;

const int N = 1010;

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

int main(){
    int n,m;
    cin>>n>>a+1>>m>>b+1;
    for(int i=0;i<=n;i++) f[i][0] = i; //b长度为0，a有多长就删除多少个
    for(int j=0;j<=m;j++) f[0][j] = j; //a长度为0，b有多长a就添加多少个
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1);
            if(a[i]==b[j]) f[i][j] = min(f[i][j],f[i-1][j-1]);
            else f[i][j] = min(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

编辑距离

题目链接

跟上一题一样，只是求多次编辑距离即可

代码

#include<iostream>
#include<cstring>

using namespace std;

const int N=15,M=1010;
char str[M][N];
int f[N][N];

int editor_distance(char a[], char b[]){
    int la = strlen(a+1), lb = strlen(b+1);
    for(int i=1;i<=la;i++) f[i][0] = i;
    for(int j=1;j<=lb;j++) f[0][j] = j;
    for(int i=1;i<=la;i++){
        for(int j=1;j<=lb;j++){
            f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1);
            f[i][j] = min(f[i][j],f[i-1][j-1]+(a[i]!=b[j]));
        }
    }
    return f[la][lb];
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>str[i]+1;
    while(m--){
        char s[N];
        int limit;
        cin>>s+1>>limit;
        int res=0;
        for(int i=0;i<n;i++){
            if(editor_distance(str[i],s)<=limit){
                res++;
            }
        }
        cout<<res<<endl;
    }
}

区间DP

石子合并

看这里动态规划学习-基础篇1

计数类DP

整数划分

题目链接

这个题目有两种状态的表示方法

完全背包法

int-1.png

可以把这个问题看成前面的数每个数取多少次最后组合的值为n这样一个完全背包问题

朴素代码

#include<iostream>

using namespace std;

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

int f[N][N];

int main(){
    int n;
    cin>>n;
    for(int i=0;i<=n;i++) f[i][0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            f[i][j] = f[i-1][j];
            if(j>=i) f[i][j] = (f[i-1][j]+f[i][j-i])%mod;
        }
    }
    cout<<f[n][n]<<endl;
    return 0;
}

空间优化

#include<iostream>

using namespace std;

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

int f[N];

int main(){
    int n;
    cin>>n;
    f[0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            f[j] = (f[j]+f[j-i])%mod;
        }
    }
    cout<<f[n]<<endl;
    return 0;
}

动态规划法

int-2.png

代码

#include<iostream>

using namespace std;

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

int f[N][N];

int main(){
    int n;
    cin>>n;
    f[0][0] = 1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            f[i][j] = (f[i-1][j-1]+f[i-j][j])%mod;
        }
    }
    int res = 0;
    for(int i=1;i<=n;i++) res = (res+f[n][i])%mod;
    cout<<res<<endl;
    return 0;
}

数位统计DP

计数问题

题目链接

用一下视频讨论区的图

number.png

代码

#include<iostream>
#include<vector>

using namespace std;

int get(vector<int> num, int l, int r){
    int res = 0;
    for(int i=l;i>=r;i--) res = res*10 + num[i];
    return res;
}

int pow10(int x){
    int res = 1;
    while(x--) res*=10;
    return res;
}

int count(int n, int x){
   if(n==0) return 0;
   
   int ans=0;
   vector<int> num;
   while(n){
       num.push_back(n%10);
       n/=10;
   }
   n = num.size();
   
   for(int i=n-1-!x;i>=0;i--){
       if(i!=n-1){
           ans += (get(num,n-1,i+1)-!x)*pow10(i);
       }
       if(num[i]==x) ans += get(num,i-1,0) + 1;
       else if(num[i]>x) ans += pow10(i); 
   }
   
   return ans;
   
}

int main(){
    int a,b;
    while(cin>>a>>b,a|b){
        if(a>b) swap(a,b);
        for(int i=0;i<=9;i++){
            cout<<count(b,i)-count(a-1,i)<<" ";
        }
        cout<<endl;
    }
}

状态压缩DP

蒙德里安的梦想

题目链接

放下y总手绘图

sta-1.png

代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef long long LL;

const int N=12, M=1<<N;

LL f[N][M];
vector<int> state[M];
bool st[M];

int main(){
    int n,m;
    while(cin>>n>>m,n||m){
        for(int i=0;i<1<<n;i++){
            int cnt = 0;
            bool is_valid = true;
            for(int j=0;j<n;j++){
                if((i>>j)&1){
                    if(cnt&1){
                        is_valid = false;
                        break;
                    }
                    cnt=0;
                }else cnt++;
            }
            if(cnt&1) is_valid = false;
            st[i] = is_valid;
        }
        for(int i=0;i<1<<n;i++){
            state[i].clear();
            for(int j=0;j<1<<n;j++){
                if((i&j)==0&&st[i|j]){
                    state[i].push_back(j);
                }
            }
        }
        
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for(int i=1;i<=m;i++){
            for(int j=0;j<1<<n;j++){
                for(auto k:state[j]){
                    f[i][j] += f[i-1][k];
                }
            }
        }
        cout<<f[m][0]<<endl;
    }

    return 0;
}

最短Hamilton路径

题目链接

sta-2.png

代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 20, M = 1 << N;

int f[M][N];
int w[N][N];

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j =0;j<n;j++){
            cin>>w[i][j];
        }
    }
    
    memset(f,0x3f,sizeof f);
    f[1][0] = 0;//从0到0只有0这1个点被经过且距离为0
    
    for(int i=0;i<1<<n;i++){
        for(int j=0;j<n;j++){
            if((i>>j)&1){
                for(int k=0;k<n;k++){
                    if((i>>k)&1){
                        f[i][j] = min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
                    }
                }
            }
        }
    }
    cout<<f[(1<<n)-1][n-1]<<endl;
    return 0;
}

树形DP

没有上司的舞会

tree.png

这里有个题解挺详细，放一下里面的图

tree1.png

代码

链表建树可以看这个视频的树和图的存储 01:16:00

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 6100;

int happy[N];
int h[N],e[N],ne[N],idx; //链表建树
bool has_fa[N];
int f[N][2];

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++; 
}

void dfs(int u){
    f[u][1] = happy[u];
    for(int i=h[u];~i;i=ne[i]){
        int j = e[i];
        dfs(j);
        f[u][0] += max(f[j][0],f[j][1]);
        f[u][1] += f[j][0];
    }
}

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>happy[i];
    memset(h,-1,sizeof h);
    for(int i=1;i<=n-1;i++){
        int l,k;
        cin>>l>>k;
        add(k,l);
        has_fa[l] = true;
    }
    int root=1;
    while(has_fa[root]) root++;
    dfs(root);
    cout<<max(f[root][0],f[root][1])<<endl;
}

记忆化搜索

滑雪

题目链接

memsearch.png

代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 310;

int n,m;
int f[N][N];
int h[N][N];
int dx[] = {-1,1,0,0}, dy[] = {0,0,-1,1};

int dp(int x, int y){
    int &v = f[x][y];
    if(v!=-1) return v;
    
    v = 1;
    for(int i=0;i<4;i++){
        int a=x+dx[i],b=y+dy[i];
        if(a>0&&a<=n&&b>0&&b<=m&&h[x][y]>h[a][b]){
            v = max(v,dp(a,b)+1);
        }
    }
    return v;
}


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

结语

基础题型大概就写到这里了，找实习也差不多告一段落了，后面应该好好写论文了，有缘再更。