[数据结构与算法]7.1 基础DP

7.1 基础DP

DP在紫书那里也有一个单章介绍这个专项，不过当时并没有正式的介绍DP思想而是从例题直接入手的，黑书这里从基础开始一步一步讲解。

首先DP和贪心，分治法一样，DP并不指一个特定的算法，而是一种解决问题的算法思想，简单解释来说是将一个复杂的问题分割成相对简单的子问题，再一个个解决，最后得到复杂问题的最优解。

与分治法不同的是，分治法的子问题之间互相独立，每个子问题能够独立解决。DP的子问题，之间互相联系，最终解即是子问题的其中之一。

7.1.1 硬币问题

有n种硬币，面值分别为v1，v2······，每种都有无限多。给定非负整数S，可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值和最大值。

分析：几乎可以说是动态规划最为经典的问题之一了，紫书上已经做了非常充分的从求解到打印解的过程，这里只引用代码：

minv[0]=maxv[0]=0;//分别表示最短路和最长路的路径长度
for (int i=1;i<=S;i++) {minv[i]=INF; maxv[i]=-INF;}
for (int i=1;i<=S;i++) for (int j=1;j<=n;j++) if (i>=v[j]){
	//i表示状态结点,j表示第j种面值(状态转移方程)
	minv[i]=min(minv[i],minv[i-v[j]]+1); maxv[i]=max(maxv[i],maxv[i-v[j]]+1);
}//输出minv[S]和maxv[S]即可 
void print_ans(int *d,int S){///这里的调用的d数组分别为minv和maxv
	for (int i=1;i<=n;i++) if (S>=v[i]&&d[S]==d[S-v[i]]+1){
		printf("%d ",i); print_ans(S-v[i]); break;
	}
} 

用的写法是类似记忆化搜索而非完全递归的写法，虽然黑书上记忆化搜索和递推是第二节的内容但其实放到第一节也无可厚非。

不过黑书在这里是将硬币面值放在了循环的外层，硬币和放在了内层，代码的编写上避免了if的判断(代码详见hdu2069)。

黑书后面拓展了一类问题：

所有硬币组合

有n种硬币，面值分别为v1，v2·····vn，数量无限。输入非负整数s，选用硬币，使其和为s，输出所有可能的硬币组合总数。

如果问题只是这样，那和前面的硬币问题几乎没有任何区别。事实上会给上一个限制：可能的硬币组合使用的硬币个数不能超过x。

分析：添加了一个条件后明显感觉到dp的状态设置的太简单了，如果用dp[i]只能存储硬币组合总数，不能确定满足一定条件的硬币个数。

那如果给dp的状态添加一个限制来满足条件，就又出现了另一个问题：因为我们没有记录每种组合使用的硬币总数，我们无法确定dp后的新状态是否满足条件。

其实思考到这步，解决的方案也基本出来了：既然没有缺少硬币组合的硬币总数这个属性，我们给它添加一个即可。用dp[i][j]表示硬币和为i，使用硬币个数为j的方案总数，进行一个二维dp，最终将dp[s][0]~dp[s][100]想加即可。样题如下：

hdu 2069 “Coin Change”

题面请点击这里

分析：面值是给定的，就按照上面的思路打代码就可以了，dp的代码还是不太难的，不过对于多维度dp最需要注意的还是将哪个属性放在循环的哪一层。

可以发现紫书和黑书在设置属性的循环层数这里还是有区别的：

#include<cstdio>
using namespace std;
int dp[251][101]={0};//dp[i][j]表示硬币和为i,使用硬币个数为j的方案总数 
int type[5]={1,5,10,25,50};//5种给定的面值
void solve(){dp[0][0]=1;//初始化
	//由于硬币的个数只是为了满足条件而附带的属性,所以主要还是以硬币和进行最内层的循环 
	//将硬币的面值放在最外层的循环是为了提高代码的简洁性和效率,事实上放在内层也是可行的 
	for (int i=0;i<5;i++) for (int j=1;j<101;j++) for (int k=type[i];k<251;k++) dp[k][j]+=dp[k-type[i]][j-1]; 
} 
int main(){int s,ans[251]={0}; solve();//ans[i]为硬币个数不大于100硬币和为i的方案总数
	for (int i=0;i<251;i++) for (int j=0;j<101;j++) ans[i]+=dp[i][j];//相加即可
	while (~scanf("%d",&s)) printf("%d\n",ans[s]); return 0; 
} 

虽然没有学习记忆化搜索，但这种存储方案非纯递归的做法已经十分接近于记忆化搜索了。

7.1.2 0/1背包

硬币问题几乎是dp问题最经典的问题之一，0/1背包问题就是最经典的问题没有之一。

dp问题中国的背包问题分为物品无限的背包问题和0/1背包问题，每种物品有无限多个就是物品无限的背包问题，每种物品只有1个就是0/1背包问题。当然还有种最简单的，一般背包问题，就是里面的物品甚至可以分割，这种用贪心法来处理就可以了。

0/1背包的解决方紫书学习那里已经介绍过了，就不重复介绍了。其实就是用d(i,j)表示将前i个物品装到容量为j的背包中的最大重量，d(i,j)=max(d(i-1,j),d(i-1,j-V[i])+W[i])(代表是否放入第i个物品)，答案为d[n][C]。

hdu 2602 “Bone Collector”

就是0/1背包问题。

分析：根据上面的状态转移方程有代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct bone{int v,w;}a[1011];//v为体积,w为价值
int n,v,dp[1011][1011];//dp[i][j]表示将前i个物品装到容量为j的背包中的最大重量
int solve(){memset(dp,0,sizeof(dp));
	for (int i=1;i<=n;i++) for (int j=0;j<=v;j++){
		if (a[i].v>j) dp[i][j]=dp[i-1][j];//第i个物体太大了装不下
		else dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i].v]+a[i].w);//装或者不装第i个物体 
	} return dp[n][v]; 
}
int main(){int T; scanf("%d",&T);
	for (int i=0;i<T;i++){scanf("%d%d",&n,&v);
		for (int j=1;j<=n;j++) scanf("%d",&a[j].w); for (int j=1;j<=n;j++) scanf("%d",&a[j].v);
		printf("%d\n",solve());
	} return 0;
} 

紫书上的写法基本一致，就是多一种一遍输入一边处理的写法，但由于我们这里不是输入一个v输入一个w，所以也不能用那种写法。

紫书和黑书这里同时介绍了一种小技巧——滚动数组，即用一个一维的数组来实现二维的dp，以节省空间。因为观察可以发现，每一行都是通过正上方元素的值和左上方元素的值取较大值得到的。那么我们将上一行当作原本的数组遗留在那里，用新的一行的元素来覆盖原来的一行就好了。

memset(dp,0,sizeof(dp))
for (int i=1;i<=n;i++){scanf("%d%d",&V,&W);
	for (int j=v;j>=0;j--) if (j>=V) dp[j]=max(dp[j],dp[j-V]+W);
}

因为是一个逆序的更新，dp[j-V]中仍保存着上一行没有更改过的值，效果和二维dp是一样的。

这么做，虽然能够节省空间，但同样由于只保留了最后的状态，所以会损失很多信息，导致无法输出方案。

完全背包就是在内层的循环中进行相反顺序的更新：

memset(dp,0,sizeof(dp))
for (int i=1;i<=n;i++){scanf("%d%d",&V,&W);
	for (int j=0;j<=v;j++) if (j>=V) dp[j]=max(dp[j],dp[j-V]+W);
}

hdu 1024 “Max Sum Plus Plus”

将给定的长度为n的序列，选出m个不相交的子序列，使得这m个子序列的元素和最大。

分析：dp状态的定义还是很好想的，dp[i][j]表示前面j个数分成了i段的最大值，转移方程其实就是看第j个数字放在的位置。

第一种可能是第j个数字和最后的区间并成一组，于是考虑之前的j-1个数字分成i段的最大情况，在最后的区间并入即可，于是dp[i][j]=dp[i][j-1]+num[j]。

第二种可能是第j个数字单独的分成一段，前j-1个数中的前若干个数分成不包括第j-1个数在内的i-1段。

于是有：dp[i][j]=max(dp[[i][j-1],dp[i-1][k])+num[j]，其中k=i-1(因为i-1段最少占用i-1个数)，i，…，j-2(第j-1个数不能选取)。

当然这么做无论从空间还是时间上都是不合格的，不过我们注意到第二种可能，前j-1个数中的前若干个数分成不包括第j-1个数在内的i-1段，可以直接将它定义为一个新的状态pre[j]表示不包括num[j]的前i个数的最大和。于是有：

dp[i][j]=max(dp[i][j-1],pre[j-1])+num[j]。

再用滚动数组优化掉第一维，dp[j]=max(dp[j-1],pre[j-1])+num[j]。

pre[j-1]=max{dp[k]}，k=i-1，i，…，j-2，需要注意到的是，由于k最大等到j-2，pre的更新始终要慢dp更新一步，但为了更新顺利，也需要一个变量在更新pre[j-1]的同时，记录pre[j]的值，pre数组最大只求到pre[n-1]，最终返回的是变量的值。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x7ffffff;
int num[1000010],dp[1000010],pre[1000010];//dp[j]在第i次循环中表示j个数分成i段的最大值
//pre[j]表示不包括num[j]的前i个数的最大和 
int solve(int m,int n){memset(dp,0,sizeof(dp)); memset(pre,0,sizeof(pre)); int ans;
	for(int i=1;i<=m;i++){ans=-INF;//第i次循环,滚动数组ans得到的即是n个数分成i段的最大值(无论分成前多少位) 
        for(int j=i;j<=n;j++){//此时的d[j-1]已经更新成j个数分成i段的最大值,pre还是i-1段的情况 
            dp[j]=max(dp[j-1],pre[j-1])+num[j];//满足d[i][j]=max(d[i][j-1],pre[j-1])+num[j] 
            pre[j-1]=ans; ans=max(ans,dp[j]);//更新pre,ans相当于pre[j] 
        }
    } return ans; 
}
int main(){int m,n; 
	while (~scanf("%d%d",&m,&n)){for (int i=1;i<=n;i++) scanf("%d",&num[i]); 
		printf("%d\n",solve(m,n));
	} return 0;
} 

其实设置一个pre状态作为辅助是比较容易想到的，我个人觉得想清楚pre数组是怎么更新的，更新的时候为什么要慢一步比较困难。

hdu 4576 “Robot”

多组输入n,m,l,r。表示在一个环上有n个格子，接下来输入m个w表示连续的一段命令，每个w表示机器人沿顺时针或者逆时针方向前进w格，已知机器人是从1号点出发的，输出最后机器人停在环上[l,r]区间的概率。

分析：一道非常水的概率题，我们设dp[i][j]表示第i轮落在x格的概率，i=0表示初始状态：dp[0][1]=1，dp[0][j]=0。如果我们想要在某一轮落到x，这一轮移动了w格，那么上一轮可能的位置只有(w-x+n)%n或者(w+x)%n，也就是说：

dp[i][x]=dp[i-1][(w-x+n)%n]+dp[i-1][(w+x)%n]

由于第i轮只与第i-1轮有关，可以用滚动数组。但这里存在一个问题，就是说，滚动数组经常需要考虑从哪边进行修改，但这道题目中从左修改和从右修改似乎都无法得到我们想要的结果。

我原本的打算是像上道题一样，用个pre保存上一轮的状态，但这么做很耗时。我在别人的博客中看到了一种精彩绝伦的处理方法：

#include<cstdio>
#include<cstring>
using namespace std;
int n,m,l,r,x;;
int get(int x) {if(x<=0) x+=n; if(x>n) x-=n; return x;}//保证x在圆环范围内 
double dp[2][1010];//为了避免前一轮的状态和当前轮的状态纠缠,如果前一轮的状态存储在dp[0][j],当前轮状态存储在dp[1][j] 
int main(){int m,l,r,x; 
    while(scanf("%d%d%d%d",&n,&m,&l,&r)&&(n||m||l||r)){memset(dp,0,sizeof(dp));
        int o=0; dp[o][1]=1;//最开始在1位置,存储在dp[0][j],每经历一轮将存储在dp[o][j]的状态转移到dp[o^1][j] 
        for(int i=0;i<m;i++){scanf("%d",&x); x%=n; o^=1;//避免过大或过小
            for(int j=1;j<=n;j++) 
                dp[o][j]=(dp[o^1][get(j-x)]+dp[o^1][get(j+x)])/2.0;
        }double ans=0;//落在l到r之间的概率即是,落在l,l+1··r的概率的总和 
        for(int i =l;i<=r;i++) ans+=dp[o][i]; printf("%.4lf\n",ans);
    }return 0;
}

第一轮将状态存储在dp[0][j]中，第二轮将状态存储在dp[1][j]，0和1交替使用每过一轮切换一次。这样做避免了前后的状态纠缠，因为一个存储在1的位置，另一个存储在0的位置，也节省了大量的空间。而且还不需要对定义pre数组，对pre数组进行赋值，节省了大量的时间。

是不知道从哪里开始更新的滚动数组的极好的做法。

至于那个get函数，如果不这么写会超时，事实上我也不知道为什么······

hdu 5119 “Happy Matt Friends”

有N个人，每个人有一个权值，挑选一些人人并将他们的权值异或，求最后得到的值大于M的取法有多少种。

分析：这个问题首先要知道一点就是，当a先后与b进行两次异或运算，最终的结果一定为a，即a xor b xor b = a(因为b xor b =0)。

我们用dp[i][j]表示前i个数选取一定数进行异或，最终值为j的方案总数，对于dp[i][j]，除了前i-1个数选取一定数异或得到j的方案数，还有可能是前i-1个数选取一定数异或得到k，k xor a[i]=j，即：

dp[i][j]=dp[i-1][j]+dp[i-1][k]， k xor a[i]=j，之前说a xor b xor b = a，可以推测出k=j xor a[i]，于是：dp[i][j]=dp[i-1][j]+dp[i-1][j xor a[i]]。

由于i的状态只与i-1有关，可以用滚动数组，同时j xor a[i]与j的关系不确定，用和上题一样的方法进行处理。

#include<cstdio>
#include<cstring>
using namespace std;
long long dp[2][1<<20],a[41];
int main(){int T; scanf("%d",&T);
	for (int c=1;c<=T;c++){memset(dp,0,sizeof(dp)); int o=0,n,m; dp[o][0]=1;//一个数不参与异或的结果为0,方案数为1 
		scanf("%d%d",&n,&m); 
		for (int i=1;i<=n;i++) scanf("%d",&a[i]);
		for (int i=1;i<=n;i++){o^=1;//dp[i][j]=dp[i-1][j]+dp[i-1][j xor a[i]] 
			for (int j=0;j<(1<<20);j++) dp[o][j]=dp[o^1][j]+dp[o^1][j^a[i]];
		}long long ans=0;//异或得到的值大于等于m的方案总数相加即是我们最终需要的答案 
		for(int i=m;i<(1<<20);i++) ans+=dp[o][i]; 
        printf("Case #%d: %lld\n",c,ans);
	}return 0;
}

7.1.3 最长公共子序列

给定两个子序列A和B。求长度最大的公共子序列，例如1，5，2，6，8，7和2，3，5，6，9，8，4的最长公共子序列为5，6，8。

这个问题紫书那里也讲过了：

状态d(i,j)设为以Ai和Bj分别作为最后一个元素的序列的LCS长度(最长公共子序列)，如果A[i]=B[j]，那么肯定有d(i,j)=d(i-1,j-1)+1(相当于在状态(i-1,j-1)的最长公共子序列后面添加了一个A[i]=B[j])，否则，d(i,j)=max(d(i-1,j),d(i,j-1)(相当于添加后的元素被无效化了，不能增加最长公共子序列的长度)。

紫书那里讲错了，我在黑书上又验证了一遍，我写的动态规划的方法是没有任何问题的。

hdu 1159 “Common Subsequence”

求两个序列的最长公共子序列。

分析：代码如下：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[1005][1005];//dp[i][j]表示从开头到第i位的x的子序列和从开头到第j位的的y的子序列的最长公共子序列 
int LCS(string x,string y){memset(dp,0,sizeof(dp));
	for (int i=1;i<=x.size();i++) for (int j=1;j<=y.size();j++){
		if (x[i-1]==y[j-1]) dp[i][j]=dp[i-1][j-1]+1;
		else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);	
	} return dp[x.size()][y.size()];
}
int main(){string s1,s2;
	while (cin>>s1>>s2){cout<<LCS(s1,s2)<<endl;} return 0;
}

可以进行滚动数组的优化。

7.1.4 最长递增子序列

给定n个整数，按从左到右的顺序选出尽可能多的整数，组成一个严格上升子序列。

这里只提供O(nlogn)复杂度的简化代码，具体的讲解过程，还是看之前紫书的博客。

int LIS(){int len=1,d[MAXN]; d[1]=high[1];
	for (int i=2;i<=n;i++){
		if (high[i]>d[len]) d[++len]=high[i];
		else{int j=lower_bound(d+1,d+len+1,high[i])-d; d[j]=high[i];}
	} return len;
}

基础习题

hdu 2018 “母牛的故事”

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

分析：简单的dp基础题，用dp[i]表示第i年的母牛头数，第i年的母牛头数等于第i-1年原本的母牛头数+第i年能够生育的母牛头数，一只牛出生后的三年后可以生育，于是：

dp[i]=dp[i-1]+dp[i-3]。

代码如下：

#include<cstdio>
using namespace std;
long long dp[60];
void init(){dp[1]=1; dp[2]=2; dp[3]=3;//初始状态第一年有一头母牛,第二年两头,第三年三头 
	for (int i=4;i<55;i++) dp[i]=dp[i-1]+dp[i-3];
}
int main(){init(); int x;
	while (scanf("%d",&x)&&x!=0){printf("%d\n",dp[x]);}return 0;
}

hdu 2041 “超级楼梯”

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

分析：斐波那契数列就是说：

#include<cstdio>
using namespace std;
long long dp[60];//斐波那契数列 
void init(){dp[1]=1; dp[2]=1; 
	for (int i=3;i<55;i++) dp[i]=dp[i-1]+dp[i-2];
}
int main(){init(); int n,x; scanf("%d",&n);
	while (n--){scanf("%d",&x); printf("%d\n",dp[x]);} return 0; 
}

hdu 2044 “一只小蜜蜂”

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。

分析：对于位置i，我们可以从位置i-1前往，也可以从位置i-2前往，这么想的话和斐波那契数列是一样的：

#include<cstdio>
#include<cstring> 
using namespace std;
long long dp[60];//dp[i]表示从a到位置i的可能路径数,位置i可以通过位置i-1和位置i-2得到 
long long solve(int a,int b){dp[a]=1; dp[a+1]=1; 
	for (int i=a+2;i<=b;i++) dp[i]=dp[i-1]+dp[i-2]; return dp[b];
}
int main(){int n,a,b; scanf("%d",&n);
	while (n--){scanf("%d%d",&a,&b); printf("%lld\n",solve(a,b));} return 0; 
}

hdu 2050 “折线分割平面”

我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分。

分析：对于新增的一条折线，最好的情况是与之前存在的每条直线相交两次，多一个交点产生两个区域，所以多出的部分为2*2*(i-1)+1。

#include<cstdio>
#include<cstring> 
using namespace std;
long long dp[10001];//dp[i]表示从a到位置i的可能路径数,位置i可以通过位置i-1和位置i-2得到 
void init(){dp[0]=0; dp[1]=2; 
	for (int i=2;i<=10001;i++) dp[i]=dp[i-1]+4*(i-1)+1; 
}
int main(){int n,x; init(); scanf("%d",&n);
	while (n--){scanf("%d",&x); printf("%lld\n",dp[x]);} return 0; 
}

(题面不严谨)

hdu 2182 “Frog”

有一只青蛙，在一条长度为n的路上，总共可以跳k次，每次跳的t个单元满足(a<=t<=b)，不能后退，而路上每个位置都放置有昆虫，求青蛙最多可以吃到的昆虫数。

分析：状态就比较直接，用dp[i][j]表示跳了i次后到达j位置的最多能够吃到的昆虫数，num[i]表示第i个位置能吃到的虫子，那么有：

dp[i][j]=max{dp[i-1][j-r]}，j-b<=r<=j-a。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;//dp[i][j]表示跳了i次后到达j位置的最多能够吃到的昆虫数,num[i]表示第i个位置能吃到的虫子 
int main(){int t,n,a,b,k,num[105],dp[105][105]; scanf("%d",&t); 
    while(t--){scanf("%d%d%d%d",&n,&a,&b,&k); memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++) scanf("%d",&num[i]);//dp[i][j]=max{dp[i-1][j-r]},j-b<=r<=j-a。
        for(int i=1;i<=k;i++) for(int j=1;j<=n;j++) for(int r=j+a;r<=j+b&&r<=n;r++)
        	dp[i][r]=max(dp[i][r],dp[i-1][j]+num[r]);
        printf("%d\n",dp[k][n]+num[1]);//加上起点的昆虫数 
    } return 0;
}

背包问题

hdu 2159 “FATE”

最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？

分析：dp[i]表示消耗i点耐久度下，最多能获得的经验值，v[i]表示第i只怪消耗的耐久度，w[i]表示第i只怪获得的经验值，那么有：

dp[j]=dp[j-v[i]]+w[i]，1<=i<=k。

通过dp得到状态对应的值之后，寻找最小的能够至少获得n点经验值的耐久度i，m-i即是剩余的耐久度，找不到说明无法升级。

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[10010],sum[10010];//dp[i]表示消耗i点耐久度下最多能获得的经验值,sum[i]记录当前的杀怪个数 
int main(){int n,m,k,s,v[10010],w[10010];//v[i]表示第i只怪消耗的耐久度,w[i]表示第i只怪获得的经验值 
	while (~scanf("%d%d%d%d",&n,&m,&k,&s)){memset(dp,0,sizeof(dp)); memset(sum,0,sizeof(sum));
		for (int i=1;i<=k;i++) scanf("%d%d",&w[i],&v[i]);
		//状态转移的同时需要考虑当前状态之前的状态杀怪个数不能大于等于s否则转移之后会大于s 
		for (int i=1;i<=k;i++) for (int j=v[i];j<=m&&sum[j-v[i]]<s;j++) if(dp[j]<dp[j-v[i]]+w[i])
        	{dp[j]=dp[j-v[i]]+w[i]; sum[j]=sum[j-v[i]]+1;}
    	for(int i=0;i<=m;i++){//寻找能够至少获得n点经验的耐久度i,m-i即是剩余的耐久度,否则没有合适的耐久度 
            if(dp[i]>=n){printf("%d\n",m-i); break;} else if(i==m) printf("-1\n");
        }
	} return 0;
}

hdu 2844 “Coins”

给了n件物品，每件物品有对应的价值Ai和数量Ci，求1-m价值之间有多少价值能够通过这些物品的价值凑出来。

分析：数量最大到1000，n最大为100，100*1000=100000的规模直接做很有可能会超时，所以有一种优化的方法称为多重背包。

假设价值为1的物品有20个，完全背包来看我们需要进行20次状态转移，但如果我们将20通过类似于快速幂的方法进行分割：

20=1+2+4+8+5。

那么1-20中的每一个状态我们都能由这五个状态组成，并且转移次数从20次减少了5次。优化结束后相当于，每种新的面值转化成只有一张，就变成一个基础的0/1背包问题。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;//s数组存储优化后的面值,dp[i]=i表示价值i能够凑出 
int a[100050],c[100050],s[100050],dp[100050];
int main(){int n,m; 
    while(scanf("%d%d",&n,&m)){if(n==0&&m==0) break; int num=0;//num表示优化后面值的个数 
        for(int i=0;i<n;i++) scanf("%d",&a[i]); for(int i=0;i<n;i++) scanf("%d",&c[i]);
        for(int i=0;i<n;i++){int k=1,tmp=c[i];//将c[i]尽可能的分解为二进制的和 
            while(tmp>k){s[++num]=a[i]*k; tmp-=k; k*=2;}//将分解出的面值进行存储
            s[++num]=a[i]*tmp;//剩余的也作为一种面值存储起来 
        } memset(dp,0,sizeof(dp));
		//每种新的面值转化成只有一张,就变成一个基础的0/1背包问题(滚动数组) 
		for(int i=1;i<=num;i++) for(int j=m;j>=s[i];j--) dp[j]=max(dp[j],dp[j-s[i]]+s[i]); 
    	int ans=0;
    	for(int i=1;i<=m;i++) if(dp[i]==i) ans++; printf("%d\n",ans);
    } return 0; 
}

hdu 2955 “Robberies”

题面请点击这里

分析：模板是0/1背包这点是没有问题的，但是状态的转移不是加法而是乘法，因为不被抓的概率是相乘而不是相加(否则就变成偷的越多越不容易被抓到)。

找答案还是一样的逆序查找：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;//dp[i]为抢劫到价值为i的银行不被捉的最大概率 
int main(){int T,n,w[105],sum; double p[105],P,dp[10005]; scanf("%d",&T); 
	while (T--){scanf("%lf%d",&P,&n); sum=0;//sum为所有银行的价值总和,即为背包的最大容量 
		for (int i=1;i<=n;i++){scanf("%d%lf",&w[i],&p[i]); sum+=w[i];}
		memset(dp,0,sizeof(dp)); dp[0]=1.0;//一个银行不抢,不被抓的概率为百分之百 
		//p[i]为抢劫第i个银行被抓的概率,乘以1-p[i]就是不被抓的概率 
		for(int i=1;i<=n;i++) for(int j=sum;j>=w[i];j--){	 
			dp[j]=max(dp[j],dp[j-w[i]]*(1.0-p[i]));
		}//逆序遍历,直到找到一种金额i被捉的最小概率(1-dp[i])小于等于P,即是在P概率下能够抢劫到的最大金额 
		for(int i=sum;i>=0;i--)	if((1.0-dp[i])<=P){printf("%d\n",i); break;}
	} return 0;
}

poj 1015 “Jury Compromise”

LIS

hdu 1003 “Max Sum”

求一个序列子序列元素和的最大值。

分析：关于最大连续和，一般常见的解法有：暴力法，前缀和，分治法，累积遍历法，动态规划。对于这道题的数据范围用紫书上介绍过的分治法就可以解决，这里主要介绍后面两种做法。

动态规划：

用dp[i]表示以第i个数结尾的子序列元素和的最大值，那么dp[i]=max{dp[i-1]+num[i],num[i]}。

最后求dp[i]，1<=i<=n的最大值即可，属于O(n)的做法。

前缀和：

直接前缀和是O(n²)的做法，但如果我们在计算前缀和的同时维护当前计算出的所有前缀和中的最小值，用当前计算出的整个序列的和减去这个最小值记作max2[i]，最终结果子序列一定能表示成max2[i]的结果(至于为什么，用反证法想一想就能明白了)。

最后求max2[i]，1<=i<=n的最大值，也是O(n)的做法。

累计遍历法：

详见这篇博客，和动态规划法关系不大

hdu 1087 “Super Jumping”

题面请点击这里

分析：LIS问题求的是最长的递增子序列，这个问题求的是递增子序列中元素和最大的那个，一样用dp[i]表示以第i个数结尾的元素和最大的递增子序列元素之和，那么有：

dp[i]=max{dp[j]}+num[i]，0<j<i，num[j]<num[i]

最后求，dp[i]的最大值。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;//dp[i]表示以第i个数结尾的元素和最大的递增子序列元素之和 
int main(){int n,num[1010],dp[1010]; 
	while(scanf("%d",&n)&&n){memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++) scanf("%d",&num[i]); dp[1]=num[1];//由于所有数字为正数,dp[1]=num[1] 
		for(int i=2;i<=n;i++){dp[i]=num[i];
			for(int j=1;j<i;j++) if (num[j]<num[i]) dp[i]=max(dp[j]+num[i],dp[i]);
		}int ans=-0x3f3f3f3f;//求dp[i]的最大值 
		for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
		printf("%d\n",ans);
	} return 0;
}

LCS

hdu 1503 “Advanced Fruits”

输入两个字符串，输入一个最短的字符串使得两个字符串都为这个字符串序列的子序列。

分析：事实上这个字符串就是两个字符串相加除去一个最大公共子序列的部分，问题就在于我们如何打印这个结果。

我的第一个想法是保存每一种状态时的路径，但是路径也需要时间。第二种方法，是用flag标记出dp过程中每一步的选择，然后根据标记往回寻找方案。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;//dp[i][j]表示s1前i位和s2前j位最大公共子序列的长度
char s1[110],s2[110]; int dp[110][110],flag[110][110];
void print_ans(int x,int y){if(x==0&&y==0) return;//回退结束 
	//flag[x][y]=0,说明是公共位,打印s1的第x位或者s2的第y位,然后回退到dp[x-1][y-1]的状态 
    if(flag[x][y]==0){print_ans(x-1,y-1); printf("%c",s1[x-1]);}
    //flag[x][y]=1,说明当前状态继承的是(x,y-1)的状态,打印s2的第y位,回退到dp[x][y-1]的状态 
    else if(flag[x][y]==1){print_ans(x,y-1); printf("%c",s2[y-1]);}
    //flag[x][y]=0,同理打印s1的第x位,回退到dp[x-1][y]的状态 
	else{print_ans(x-1,y); printf("%c",s1[x-1]);}
} 
int main(){
	while (~scanf("%s%s",s1,s2)){memset(dp,0,sizeof(dp));
		//初始化,当某一个序列已经回退完后,只能打印另一个序列的元素 
		for(int i=0;i<=strlen(s1);i++) flag[i][0]=-1;//s2回退完,打印s1的元素 
        for(int i=0;i<=strlen(s2);i++) flag[0][i]=1;//s1回退完,打印s2的元素
		for(int i=1;i<=strlen(s1);i++) for(int j=1;j<=strlen(s2);j++){
            if(s1[i-1]==s2[j-1]) {dp[i][j]=dp[i-1][j-1]+1; flag[i][j]=0;}//表示这个状态属公共部分
            //s1的第i位和s2的第j位不相等,dp[i][j-1]<dp[i-1][j]说明s1前i位s2前j位的状态
			//继承的是s1前i-1位,s2前j位的状态,此时s1的第i位相当于是"无用的",打印即可 
			else if(dp[i][j-1]<dp[i-1][j]) {dp[i][j]=dp[i-1][j]; flag[i][j]=-1;}
            else {dp[i][j]=dp[i][j-1]; flag[i][j]=1;}//同理标记单独输出s2的第j位 
        } print_ans(strlen(s1),strlen(s2)); printf("\n");
	} return 0;
}

需要注意的一点就是回退时，当某个序列回退完全了，此时不用再看flag的值直接往前输出另一个序列即可，所以需要对flag[i][0]和flag[0][j]进行一次初始化。