描述

针对满足特定条件的一类问题,对各状态维度进行分阶段,有顺序,无重复,决策性的遍历求解。

要素

状态,阶段,决策;

条件

子问题重叠性,无后效性,最优子结构性质;

常见dp

• LIS问题
• LCS问题
• 数字三角形
• 0/1背包
• 完全背包
• 多重背包
• 分组背包
• 区间dp

例题讲解

现在我们有N个配件,他们有不同的价值. 但是我们背包的容量是有限的,因为我们只有一个一级包, 所以我们最多可以装V重量的东西. 但是为了能更好的吃到鸡(不存在的)我们要携带更有价值的配件,请问我们最多能拿多少价值的配件来当快递员呢??

分析:很经典的0/1背包问题,直接dp求解即可,还可以顺便空间压缩.

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const ll size = 1e5+5;
ll v[size],w[size],dp[size];
int main()
{
	int T;cin >> T;
	while(T--)
	{
		ll n,V;cin >> n >> V;
		for(int i = 1;i <= n;++i)
			scanf("%lld",v+i);
		for(int i = 1;i <= n;++i)
			scanf("%lld",w+i);
		for(int i = 0;i <= V;++i) dp[i] = 0;
		for(int i = 1;i <= n;++i)
			for(int j = V;j >= 0;--j)
				if(j >= w[i]) dp[j] =  max(dp[j],dp[j-w[i]]+v[i]);
		cout << dp[V] << endl;
	}
	return 0;
 } 

在 ACM 能够开展之前，必须准备预算，并获得必要的财力支持。该活动的主要收入来自于 Irreversibly Bound Money (IBM)。思路很简单。任何时候，某位 ACM 会员有少量的钱时，他将所有的硬币投入到小猪储钱罐中。这个过程不可逆，因为只有把小猪储钱罐打碎才能取出硬币。在足够长的时间之后，小猪储钱罐中有了足够的现金，用于支付 ACM 活动所需的花费。
但是，小猪储钱罐存在一个大的问题，即无法确定其中有多少钱。因此，我们可能在打碎小猪储钱罐之后，发现里面的钱不够。显然，我们希望避免这种不愉快的情况。唯一的可能是，称一下小猪储钱罐的重量，并尝试猜测里面的有多少硬币。假定我们能够精确判断小猪储钱罐的重量，并且我们也知道给定币种的所有硬币的重量。那么，我们可以保证小猪储钱罐中最少有多少钱。
你的任务是找出最差的情形，即判断小猪储钱罐中的硬币最少有多少钱。我们需要你的帮助。不能再贸然打碎小猪储钱罐了！

分析:很直接的完全背包问题

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const ll INF = 1e17; 
ll w[100005],v[100005],dp[100005];
int main()
{
	int T;cin >> T;
	while(T--)
	{
		int n,m,t;cin >> m >> t >> n ;m = t-m;
		for(int i = 1;i <= n;++i) scanf("%lld%lld",v+i,w+i);
		for(int i = 1;i <= m;++i) dp[i] = INF;
		for(int i = 1;i <= n;++i)
			for(int j = 0;j <= m;++j)
				if(j >= w[i])
					dp[j] = min(dp[j],dp[j-w[i]]+v[i]);
		if(dp[m]<INF)
			printf("The minimum amount of money in the piggy-bank is %lld.\n",dp[m]);
		else printf("This is impossible.\n");
	}
	return 0;
} 

郭哥与瑞瑞在玩一个游戏.
　　他们先各自写下一串字符，然后互相展示。展示过后，他们再从自己写的那串字符中依次挑出若干字符（保持原有顺序不变），组成新的一串。他们希望自己新组成的字符串与对方新组成的完全相同，并且尽可能长。
　　例如，郭哥写下abcde，瑞瑞写下aeiou，然后郭哥挑出自己那串里的第1和第5个字符组成新串ae，瑞瑞挑出自己那串中的第1、2个字符，也组成字符串ae。ae就是他们能共同挑出的最长串。
　　现在，郭哥和瑞瑞分别写出了自己的字符串，请帮他们算一下他们能共同挑出组成的字符串最长有多长。

分析:套LCS模板即可.

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const ll INF = 1e17;
char s1[100005],s2[100005];
int dp[1005][1005];
int main()
{
	while(~scanf("%s%s",s1+1,s2+1))
	{
		int l1 = strlen(s1+1),l2 = strlen(s2+1);
		for(int i = 1;i <= l1;++i)
			for(int j = 1;j <= l2;++j)
				if(s1[i]==s2[j]) dp[i][j] = dp[i-1][j-1]+1;
				else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
		printf("%d\n",dp[l1][l2]);
	}
	return 0;
}

总结:dp一般情况下只需找出状态转移方程即可不讨论程序细节的求解.