二维路径类问题

路径类

P1216 P1002 P1004 P1854

P1130

# include<iostream>
using namespace std;

const int N=2003;
int n,m;
long long a[N][N]; //小组i做第j步的用时 
long long f[N][N]; //第j步在小组i的总用时
long long ans=1e15;

int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j){
			cin>>a[i][j];
			if(j==1) f[i][j]=a[i][j];
		}
	for(int i=2;i<=n;++i)
		for(int j=1;j<=m;++j){
			if(j==1)
				f[1][i]=min(f[1][i-1],f[m][i-1])+a[1][i];
			else
				f[j][i]=min(f[j][i-1],f[j-1][i-1])+a[j][i];
		}
	for(int i=1;i<=m;++i)
		ans=min(ans,f[i][n]);
	cout<<ans;
	return 0;
}

面积类

P1169 P2701 P2733

P1387

# include<iostream>
using namespace std;

const int N=103;
int n,m,ans;
bool a[N][N];
int dp[N][N]; //以(i,j)为右下角的最大边长 

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			cin>>a[i][j];
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j){
			if(!a[i][j]) continue;
			if(i==1||j==1) dp[i][j]=1;
			else
				dp[i][j]=min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1;
			ans=max(ans,dp[i][j]);
		}
	cout<<ans;
	return 0;
}

P1681

# include<iostream>
using namespace std;

const int N=1503;
int n,m,ans;
bool a[N][N];
int dp[N][N]; //以(i,j)为右下角的最大边长 

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j){
			cin>>a[i][j];
			if(i%2!=j%2) a[i][j]=!a[i][j];
		}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j){
			if(a[i][j]!=a[i-1][j]||a[i][j]!=a[i][j-1]||a[i][j]!=a[i-1][j-1])
				dp[i][j]=1;
			else if(i==1||j==1) dp[i][j]=1;
			else
				dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
			ans=max(ans,dp[i][j]);
		}
	cout<<ans;
	return 0;
}

序列类问题

单序列

P1020 P1115 P1091

双序列

P2758

# include<iostream>
# include<string>
using namespace std;

const int N=2005;
int l1,l2,f[N][N]; //s1[0...i-1] s2[0...j-1] 的距离 
string s1,s2;

int main(){
	cin>>s1>>s2;
	l1=s1.size(),l2=s2.size();
	for(int i=1;i<=l1;++i)
		for(int j=1;j<=l2;++j){
			if(i==1&&j==1){
				if(s1[0]==s2[0]) f[1][1]=0;
				else f[1][1]=1;
			}
			else if(i==1){
				if(s1[0]==s2[j-1]) f[1][j]=f[1][j-1];
				else f[1][j]=f[1][j-1]+1;
			}
			else if(j==1){
				if(s1[i-1]==s2[0]) f[i][1]=f[i-1][1];
				else f[i][1]=f[i-1][1]+1;
			}
			else{
				if(s1[i-1]==s2[j-1])
					f[i][j]=f[i-1][j-1];
				else
					f[i][j]=min(min(f[i-1][j],f[i][j-1]),f[i-1][j-1])+1;
			}
		}
	cout<<f[l1][l2]; 
	return 0;
}

P1279

过程类问题

P1018 P1541 P1052 P1103 P1280 P1944

01背包

P1504

# include<iostream>
# include<cstring>
using namespace std;

const int N=103;
int n,t,a[N][N],cnt[N],sum[N],ma;
bool dp[N][N*N]; //第i组能否凑出j的高度 
bool f[N*N]; //能否所有组积木都凑出i 

int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		while(1){
			cin>>t;
			if(t==-1) break;
			a[i][++cnt[i]]=t;
			sum[i]+=t;
		}
		dp[i][0]=1;
		ma=max(ma,sum[i]);
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=cnt[i];++j)
			for(int k=sum[i];k>=a[i][j];--k)
				dp[i][k]=dp[i][k]||dp[i][k-a[i][j]];
	memset(f,1,sizeof(f));
	for(int i=1;i<=n;++i)
		for(int j=0;j<=ma;++j)
			f[j]=f[j]&&dp[i][j];
	for(int i=ma;i>=0;--i)
		if(f[i]){
			cout<<i<<endl;
			break;
		}
	return 0;
}

完全背包

P1586

P1474

# include<iostream>
using namespace std;

const int V=30,N=1e4+3;
int v,n,a[V];
long long dp[N];

int main(){
	cin>>v>>n;
	for(int i=1;i<=v;++i){
		cin>>a[i];
		dp[0]=1;
	}
	for(int i=1;i<=v;++i)
		for(int j=a[i];j<=n;++j)
			dp[j]+=dp[j-a[i]];
	cout<<dp[n];
	return 0;
}

计数问题

P1806 P1771 P2193 P2513

区间DP

P2734

# include<iostream>
using namespace std;

const int N=203;
int n,a[N];
int f1[N][N],f2[N][N]; //区间[i,j]中先后手的最大得分 

int main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		f1[i][i]=a[i];
	}
	for(int l=2;l<=n;++l)
		for(int i=1;i<=n-l+1;++i){
			int j=i+l-1;
			if(f2[i+1][j]+a[i]>f2[i][j-1]+a[j]){
				f1[i][j]=f2[i+1][j]+a[i];
				f2[i][j]=f1[i+1][j];
			}
			else{
				f1[i][j]=f2[i][j-1]+a[j];
				f2[i][j]=f1[i][j-1];
			}
		}
	cout<<f1[1][n]<<" "<<f2[1][n];
	return 0;
}