闫氏dp分析法笔记

本文主要是介绍闫氏dp分析法笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- [1. 01背包](https://www.acwing.com/problem/content/2/)
- 2.完全背包问题
- 3.石子合并
- 4.最长公共子序列

1. 01背包

朴素写法

#include <iostream>
#include <stdio.h>
using namespace std;const int N=1005;int f[N][N];
int n,m;
int v[N],w[N];int main(){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=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i]) f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);}}cout<<f[n][m];return 0;
}

滚动数组优化

#include <iostream>
#include <stdio.h>
using namespace std;const int N=1005;int f[N];
int n,m;
int v[N],w[N];int main(){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=m;j>=v[i];j--){f[j]=max(f[j],f[j-v[i]]+w[i]);//f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i]);}}cout<<f[m];return 0;
}

2.完全背包问题

朴素写法

#include <iostream>
#include <stdio.h>
using namespace std;const int N=1005;int f[N][N];
int n,m;
int v[N],w[N];int main(){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=0;j<=m;j++){f[i][j]=f[i-1][j];if(j>=v[i]) f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);}}cout<<f[n][m];return 0;
}

滚动数组优化

#include <iostream>
#include <stdio.h>
using namespace std;const int N=1005;int f[N];
int n,m;
int v[N],w[N];int main(){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=0;j<=m;j++){if(j>=v[i]) f[j]=max(f[j],f[j-v[i]]+w[i]);}}cout<<f[m];return 0;
}

3.石子合并

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;const int N=305;int f[N][N];
int n;
int s[N]={0};//s[N]前缀和 int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&s[i]);s[i]+=s[i-1];}//memset(f,0x3f,sizeof(f));需要多出len=1时的边界初始化f[i][j]=0 for(int len=2;len<=n;len++){//枚举区间长度 for(int i=1;i+len-1<=n;i++){//枚举左端点 int j=i+len-1;//右端点f[i][j]=1e8;for(int k=i;k<j;k++)//分界点 f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);}}printf("%d",f[1][n]);return 0;
}

4.最长公共子序列

#include <iostream>
#include <string>
#include <stdio.h>
#include <string.h>
using namespace std;const int N=1005;int n,m;
char a[N],b[N];
int f[N][N]; int main(){scanf("%d %d %s %s",&n,&m,a+1,b+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);}}printf("%d",f[n][m]);return 0;
}