AHU算法课-DP动态规划

AHU算法课-DP动态规划A-最长上升子序列入门dp题,之前写过这道题的题解点击进入这道题出的很简单,O(n2)就可以过

A-最长上升子序列

入门dp题,之前写过这道题的题解 点击进入
这道题出的很简单,O(n2)就可以过。但请思考如何降低复杂度,本题可以将复杂度下降到O(nlogn) , 方法是:因为是最长上升子序列,具有着单调性,所以通过二分查找(O(logn))代替原来的遍历查找(O(n))。这样复杂度就下降到了O(nlogn)。

O(nlogn)解法

O(n2)解法:

#include <bits/stdc++.h>
using namespace std;
int a[15000],f[15000];
int n,ans=-1;
int main()
{ 
   
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    { 
   
        scanf("%d",&a[i]);
        f[i]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}

B – 数字三角形

从上往下推,第i层第t列的由第i-1层第t-1列和第i-1层第t列转移,转移方程:
f[i][t]=a[i][t]+max(f[i-1][t],f[i-1][t-1]);
#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{ 
   
    int n;
    scanf("%d",&n);
    int a[105][105];
    int f[105][105];
    //memset(f,0,sizeof f);
    for(int i=1; i<=n; i++)
    { 
   
        for(int t=1; t<=i; t++)
        { 
   
            scanf("%d",&a[i][t]);
            //f[i][t]=0;
        }
    }
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
    { 
   
        for(int t=1;t<=i;t++)
        { 
   
            if(t==1){ 
   f[i][t]=a[i][t]+f[i-1][t];}
            else f[i][t]=a[i][t]+max(f[i-1][t],f[i-1][t-1]);
        }
    }
    int maxx=0;
    for(int i=1;i<=n;i++)
    { 
   
        //printf("%d ",f[n][i]);
        maxx=max(f[n][i],maxx);
    }
    printf("%d",maxx);
    return 0;
}

C-01背包

dp中的经典题,对于每一件物品,选择拿或者是不拿这就是dp的状态转移方式。
转移方程:dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]); (i为第i件物品,j为当前背包还剩的容量)

代码:

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[3409][12885];
int w[3409],v[3409];
int main()
{ 
   
    int n,vmax;
    scanf("%d%d",&n,&vmax);
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++)
    { 
   
        scanf("%d%d",&w[i],&v[i]);
    }
    for(int i=1;i<=n;i++)
    { 
   
        for(int j=0;j<=vmax;j++)
        { 
   
            if(j-w[i]<0){ 
   dp[i][j]=dp[i-1][j];}
            else { 
   dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);}
        }
    }
    int maxx=0;
    for(int i=1;i<=vmax;i++)
    { 
   
        maxx=max(maxx,dp[n][i]);
    }
    printf("%d",maxx);
    return 0;
}
可惜的是上面的代码会MLE,这时候就要对其进行空间优化了,在下面这几行代码中,我们知道,dp的转移只和当前层与上一层有关,那么dp用一个二维数组储存是会造成空间的大量浪费,那么只用一维数组进行优化
for(int i=1;i<=n;i++)
    { 
   
        for(int j=0;j<=vmax;j++)
        { 
   
            if(j-w[i]<0){ 
   dp[i][j]=dp[i-1][j];}
            else { 
   dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);}
        }
    }

ac代码

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[12889];
int w[3409],v[3409];
int main()
{ 
   
    int n,vmax;
    scanf("%d%d",&n,&vmax);
    memset(dp,0,sizeof dp);
    for(int i=1;i<=n;i++)
    { 
   
        scanf("%d%d",&w[i],&v[i]);
    }
    for(int i=1;i<=n;i++)
    { 
   
        for(int j=vmax;j>=0;j--)
        { 
   
            if(j>=w[i]) { 
   dp[j]=max(dp[j-w[i]]+v[i],dp[j]);}
        }
    }
    int maxx=0;
    for(int i=1;i<=vmax;i++)
    { 
   
        maxx=max(maxx,dp[i]);
    }
    printf("%d",maxx);
    return 0;
}

D – 完全背包

完全背包与01背包的区别之处在于,完全背包问题中每个物品种类有无穷多个。
1. 首先大家一定会想到这种方式:和01背包一样,只不过我在每次选某种物品时,对其的数量选的数量进行递增跑一遍。
状态转移方程: f[i][j] = max(f[i][j],f[i-1][j – k * c[i]] + k * w[i]) (0<=k*c[i]<=v)
2.然而这种方法复杂度略高,因为这样不得不进行三次for循环(枚举哪种物品,当前背包容量,对于这种物品选几个)
我们再进行优化,改变一下dp思路
我们可以把把完全背包问题转化为01背包问题来解,第i种物品最多选V/c[i]件,于是可以把第i种物品转化为v/c[i]件费用及价值均不变的物品,然后求解这个01背包问题。
即:将一种物品拆成多件物品。
我们现在dp每一个物品,dp出该种物品在不同剩余容量下的最优解,他是以每1个为单位的。考虑是否在当前所有物品总数中添加一件新的该物品
我们用i代表前i种物品,v代表包的最大承重,c[i]是第i种物品消耗的空间、w[i]是第i种物品的价值、f[i,j]是最大价值(从前i种物品取若干件放入有j个剩余空间的包)。
如果不放那么f[i][j]=f[i-1][j]
如果确定放,那么f[i][j]=f[i][j-c[i]+w[i]],为什么会是f[i][j-c[i]]+w[i]?
因为我们要考虑的是在当前基础上添加一件物品i。
就是说如果你放第i种物品,并不牵扯到第i-1种物品,所以不管你放多少件,都要在第i种商品的基础上操作
所以说递推式为:
f[i][j]=max(f[i-1][j],f[i][j-c[i]]+w[i])
3.还能继续优化吗? 我们还可以利用一个滚动数组,想01背包那样对空间进行优化。
我们先回顾01背包为什么写1维要逆序?
因为为了避免要使用的子状态收到影响。
那我们该如何写完全背包的1维优化呢?
答案是:顺序
因为第i种物品一旦出现,原来没有第i种物品的情况下可能有一个最优解,现在第i种物品 出现了,而它的加入有可能得到更优解,所以之前的状态需要进行改变,故需要正序。
所以说递推式是这样子的:
f[j] = max(f[j],f[j-c[i]]+w[i])
#include<cstring>
#include<cstdio>
#include<algorithm>
#define inf 1000000000
using namespace std;
int w[10005],v[10005],dp[10005];
int main()
{ 
   
    int repeat;
    scanf("%d",&repeat);
    while(repeat--)
    { 
   
        int x,y,n,i,j;
        memset(w,0,sizeof(w));
		memset(v,0,sizeof(v));
        scanf("%d%d",&x,&y);
        int W=y-x;
        for(i=0;i<=W;i++)dp[i]=inf;
        dp[0]=0;
        scanf("%d",&n);
        for(i=0;i<n;i++){ 
   scanf("%d%d",&v[i],&w[i]);}
        for(i=0;i<n;i++)
        { 
   
            for(j=w[i];j<=W;j++)
            { 
   
                dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        if(dp[W]<inf)printf("The minimum amount of money in the piggy-bank is %d.\n",dp[W]);
		else printf("This is impossible.\n");
    }
    return 0;
}

E-区间DP

区间dp就是在区间上进行动态规划,求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。
for(int len = 1;len<=n;len++){ 
   //枚举长度
        for(int j = 1;j+len<=n+1;j++){ 
   //枚举起点,ends<=n
            int ends = j+len - 1;
            for(int i = j;i<ends;i++){ 
   //枚举分割点,更新小区间最优解
                dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);//dp[j][ends]的意思是从j到ends和;
            }
        }
    }
自己找一个例子对着上面的板子模拟一遍就知道其中意义了。
这题就是问了两个问题,合并得到的最大的数和最小的数,因此建立两个dp数组就解决了。
值得注意的是建立的这两个dp数组的初始赋值并不一样:
dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]);是求最小值的,因此dp1要初始赋值为inf(最大值)。
dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]);求最大值,所以dp2初始赋值为0(最小值)。
但全部初始化完后不要忘记赋值dp1[i][i]=0;dp2[i][i]=0; 从i到i都没办法合并,当然是0了。
代码:
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int INF = 1000000;
int sum[105],dp1[105][105],dp2[105][105];
int main()
{ 
   
    int n;
    while(scanf("%d",&n)!=EOF)
    { 
   
        int tep;
        memset(sum,0,sizeof sum);
        memset(dp1,INF,sizeof dp1);
        memset(dp2,0,sizeof dp2);
        for(int i=1;i<=n;i++)
        { 
   
            scanf("%d",&tep);
            sum[i]=sum[i-1]+tep;
            dp1[i][i]=0;
            dp2[i][i]=0;
        }
        for(int len=2;len<=n;len++)
        { 
   
            for(int i=1;i<=n;i++)
            { 
   
                int j=i+len-1;
                if(j>n) break;
                for(int k=i;k<j;k++)
                { 
   
                    dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]);
                    dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]);
                }
            }
        }
        printf("%d %d\n",dp1[1][n],dp2[1][n]);
    }
    return 0;
}

F – 数位dp

数位dp类似于一种数学游戏,它规定了一种游戏规则,然后让你在一个范围内找符合游戏规则的数字的个数,通常这个范围是十分大的,因此传统暴力的方法必然是会超时的,这时候dp便是一个很好的选择,因为符合游戏规则的数字通常有某种递推的性质,以前计算过的数如果再计算一遍必然会导致时间复杂度上升,因此我们选择dp记忆其状态递推来进行解决问题,最后通过计数来算出答案。
对于这道题,我们不妨这样设计状态,dp[i][j]代表一共i位数字,最高位是j的windy数的个数
可以推出这样的式子:f[i][j] = sum( f[i-1][k] ) |k – j| >= 2.
也就是说dp[i][j]必然合法的windy数的个数,那么如果前面再多一个|k – j| >= 2.的数 ,也就是dp[i+1][k],进行状态转移。
上面都是很好想到的,真正难处理的是:我们上述中dp[i][j]的意思一共i位数字,最高位是j的windy数的个数,然而这个dp[i][j]统计的数字的范围是什么呢? 举个例子dp[3][5],它统计的数字范围是500-599的数字,可是题目若是让你求500-550中windy数的个数该怎么办呢?
这时候我们可以首先前缀和处理,也就是说比如让我们求100-180的windy数,我们先求0-100和0-180的windy数的个数,在将上述两个相减。
然后就是如何对于一个上限不确定的进行技术处理,举个例子进行说明:
比如95387 ,dp[1.2.3.4][1.2.3…9]这些都是一定符合的,因为其位数小于五位数。再来计算五位数的,dp[5][1.2.3.4.5.6.7.8]这些也都是可以的,这些数的范围是10000-89999。最后如何处理90000-95387这部分呢?

处理方法如下:

for(i=len-1;i;i--)
    { 
   
        for(j=0;j<w[i];j++)
        { 
   
            if(abs(w[i+1]-j)>=2){ 
   ans+=dp[i][j];}
        }
        if(abs(w[i+1]-w[i])<2) break;
    }

.
.
.

#include <bits/stdc++.h>
long long int dp[15][20];
using namespace std;
int solve(int x)
{ 
   
    int len=0;
    int w[15];
    while(x)
    { 
   
        w[++len]=x%10;
        x/=10;
    }
    w[len+1]=0;
    int ans=0;
    int i,j;
    for(i=1;i<len;i++)
    { 
   
        for(j=1;j<=9;j++)
        { 
   
            ans+=dp[i][j];
        }
    }
    for(i=1;i<w[len];i++)
    { 
   
        ans+=dp[len][i];
    }
    for(i=len-1;i;i--)
    { 
   
        for(j=0;j<w[i];j++)
        { 
   
            if(abs(w[i+1]-j)>=2){ 
   ans+=dp[i][j];}
        }
        if(abs(w[i+1]-w[i])<2) break;
    }
    return ans;
}
int main()
{ 
   
    int a,b;
    scanf("%d%d",&a,&b);
    //int tep=log10(b);
    for(int i=0;i<=9;i++){ 
   dp[1][i]=1;}
    for(int i=2;i<=10;i++)
    { 
   
        for(int t=0;t<=9;t++)
        { 
   
            if(dp[i-1][t]!=0)
            { 
   
                for(int j=t+2;j<=9;j++)
                { 
   
                    dp[i][j]+=dp[i-1][t];
                }
                for(int j=t-2;j>=0;j--)
                { 
   
                    dp[i][j]+=dp[i-1][t];
                }
            }
        }
    }
    printf("%d",solve(b+1)-solve(a));
    return 0;
}

今天的文章AHU算法课-DP动态规划分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/63570.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注