首页 > 代码库 > {dp入门}
{dp入门}
之前一直比较恐惧dp的题,暑假之前好好从头补一下。
题目链接:HihoCoder - 1037
数字三角形
dp[i][j]表示到第i层第j个房间时累计收集到的最大值,从上到下记忆化搜索即可
状态转移:dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+m[i][j];
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 int n; 6 int m[110][110]; 7 int dp[110][110]; 8 int main() 9 { 10 while(scanf("%d",&n)!=EOF) 11 { 12 memset(m,0,sizeof(m)); 13 memset(dp,0,sizeof(dp)); 14 int ans=0; 15 for(int i=1;i<=n;i++) 16 for(int j=1;j<=i;j++) 17 scanf("%d",&m[i][j]); 18 for(int i=1;i<=n;i++) 19 for(int j=1;j<=i;j++) 20 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+m[i][j]; 21 for(int i=1;i<=n;i++) 22 ans=max(ans,dp[n][i]); 23 printf("%d\n",ans); 24 } 25 }
题目链接:HihoCoder - 1038
01背包
dp[j]=max(dp[j-c[i]]+v[i],dp[j]);
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 const int maxn=520; 6 int n,m; 7 int dp[100110]; 8 int c[maxn],v[maxn]; 9 int main() 10 { 11 scanf("%d%d",&n,&m); 12 for(int i=0;i<n;i++) 13 scanf("%d%d",&c[i],&v[i]); 14 for(int i=0;i<n;i++) 15 for(int j=m;j>=c[i];j--) 16 dp[j]=max(dp[j-c[i]]+v[i],dp[j]); 17 printf("%d\n",dp[m]); 18 }
题目链接:HihoCoder - 1043
完全背包
和01背包相比只是j的顺序变了
本质是为了01背包只能选一件,完全背包可以多选
即01背包时的dp[ j-c[i] ]是上一次遍历时求出的,而完全背包用的则是本次遍历求出的值
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 const int maxn=520; 6 int n,m; 7 int dp[100110]; 8 int c[maxn],v[maxn]; 9 int main() 10 { 11 scanf("%d%d",&n,&m); 12 for(int i=0;i<n;i++) 13 scanf("%d%d",&c[i],&v[i]); 14 for(int i=0;i<n;i++) 15 for(int j=c[i];j<=m;j++) 16 dp[j]=max(dp[j-c[i]]+v[i],dp[j]); 17 printf("%d\n",dp[m]); 18 }
{dp入门}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。