动态规划笔记+经典习题十道

《算法导论》笔记

（1）动态规划与贪心算法导论

动态规划通常应用于最优化问题，即要做出一组选择以达到一个最优解。在做选择的同时，经常出现同样形式的子问题。当某一特定的子问题可能出自于多于一种选择的集合时，动态规划是很有效的；关键技术是存储每一个子问题的解，以备它重复出现。利用这种简单思想，可将时间复杂度从指数级别降低到多项式级别。

贪心算法通常也是应用于最优化问题。在这种算法中，要做出一组选择以达到一个最优解。该算法的思想是以局部最优的方式来做每一个选择。对许多问题来说，采用贪心法可以比动态规划更快地给出一个最优解。但是，不容易判断贪心法的正确性。可用回顾拟阵理论进行判断。

贪心算法与动态规划有一个显著的区别，在于使用最优子结构的顺序，前者是自顶向下。贪心算法会先做选择，在当时看起来是最优的选择，然后再求解一个结果子问题，而不是先寻找子问题的最优解，然后再做选择。

（2）动态规划导论

动态规划是通过组合子问题的解而解决整个问题的。动态规划适用于子问题不是独立的情况，即各子问题包含公共的子子问题。动态规划算法对每个子子问题只求解一次，将其结果保存在一张表中，从而避免重复计算子问题。

动态规划通常应用于最优化问题。此类问题可能有很多种可行解。每个解有一个值，而我们希望找出一个具有最优（最大或最小）值的解。称这样的解为该问题的“一个”最优解（而不是“确定的”最优解），因为可能存在多个取最优值的解。

算法设计步骤：
1）描述最优解的结构。
以正序扩展可见区域，考虑从起点到区域边界的最优解。
定义问题，假设其包含了子问题并加以证明。
定义子问题，利用子问题的最优解来构造原问题的一个最优解。
2）递归定义最优解的值。
列出包含边界情况的递归公式（形式类似于分段函数）
3）按自底向上的方式计算最优解的值。
方向由递归公式确定。
4）由计算出的结果构造一个最优解。
第1~3步构成问题的动态规划解的基础。第4步在只要求计算最优解的值时可以略去。如果的确做了第4步，则有时要在第3步的计算中记录一些附加信息，使构造一个最优解变得容易。

（3）动态规划基础

适合采用动态规划方法的最优化问题的两个要素：最优子结构和重叠子问题。注意子问题要互相独立，即不共享资源。

（4）最优子结构

如果一个问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。在这种情况下，贪心也可能适用。

寻找时遵循的模式：
1）问题的一个解可以是做一个选择，做这种选择会得到一个或多个有待解决的子问题。
2）假设对一个给定的问题，已知一个可以得出最优解的选择，不必关心如何确定这个选择。
3）在已知这个选择之后，确定哪些子问题会随之产生，以及如何最好地描述所得到的子问题空间。规则是，尽量保持这个空间简单，然后在需要时再扩充它，在合适的情况下没有必要再去尝试一个更具一般性的子问题空间。
4）利用“剪贴”技巧来证明在问题的一个最优解中，使用的子问题的解本身也必须是最优的。假设子问题的解不是最优，通过“剪除”非最优解再“贴上”最优解，就证明了可以得到原问题的一个更好的解，因此，这与得到的是最优解的假设矛盾。

最优子结构在问题域中以两种方式变化：
1）要在多少种选择中选出最优。
2）每种选择使用的子问题数量。

动态规划以自底向上的方式来利用最优子结构。也就是说，首先找到子问题的最优解，解决子问题，然后找到问题的一个最优解。

（5）重叠子问题

当一个递归算法不断地调用同一问题时，称该最优问题包含重叠子问题。子问题的空间要“很小”，也就是用来解原问题的递归算法可反复地解同样的子问题，而不是总在产生新的子问题。动态规划使用表格把时间复杂度从指数级别降低到多项式级别。

HDOJ-2084 数塔

题目

有一个形如金字塔的数塔，从顶层走到底层，若每一步只能走到相邻的结点，求经过的结点的数字之和的最大值。

思路

最优子结构： 该问题（找出从顶点出发的最大路线）的最优解包含了子问题（找出从与顶点相邻的点出发的最大路线）的一个最优解。
利用子问题的最优解来构造原问题的一个最优解： 从顶点出发的路线必定经过从与顶点相邻的点。因此，经过顶点的最大路线只能是二者之一：从顶点出发走到点（2，1），走从点（2，1）出发的最大路线；从顶点出发走到点（2，2），走从点（2，2）出发的最大路线。
递归定义最优解的值： 选择从（i,j）出发的最大路线的问题作为子问题，层编号i=1,2,…,n。第i层的列编号j=1,2,…,i。令t[i][j]表示从点(i,j)出发可能得到的最大值。

我们的最终目标是确定从(1,1)出发得到的最大值。当i==n时，路线仅包含自身的点。递归公式：
$$t[i][j]=\{\begin{array}{r}t[i][j]+max(t[i+1][j],t[i+1][j+1])，1\le i<n\\ t[i][j],i=n\end{array}$$
对于1<=i<n，t[i][j]的每一个值仅依赖于t[i+1][j]和t[i+1][j+1]的值。通过以递减i的顺序来计算t[i][j]的值。
从上往下，如果每次选择的子结点对应的子塔数值最大，则父塔数值一定最大。

【法一】递归 将父结点对应的最优解转化为子结点对应的最优解。另设数组存储子塔最大值，减少重复计算。
【法二】递推 从下往上，算出各级子塔的最优解。

代码

【法一】递归

#include<iostream>
#include<cstring>
using namespace std;
int max(int x,int y){if(x>y) return x;return y;}
int n,t[105][105],m[105][105];//m存储子塔最大值
int dfs(int i,int j){if(m[i][j]>=0) return m[i][j];if(i==n-1) return m[i][j]=t[i][j];return m[i][j]=t[i][j]+max(dfs(i+1,j),dfs(i+1,j+1));
}
int main(){int c;cin>>c;while(c--){int i,j;cin>>n;for(i=0;i<n;i++)for(j=0;j<=i;j++)cin>>t[i][j];memset(m,-1,sizeof(m));//-1表示未扩展cout<<dfs(0,0)<<endl;}return 0;
}

【法二】递推

#include<iostream>
using namespace std;
int max(int x,int y){if(x>y) return x;return y;}
int main(){int c,t[105][105]={0};cin>>c;while(c--){int n,i,j;cin>>n;for(i=0;i<n;i++)for(j=0;j<=i;j++)//注意等号cin>>t[i][j];for(i=n-1;i>=0;i--)for(j=0;j<=i;j++)t[i][j]+=max(t[i+1][j],t[i+1][j+1]);cout<<t[0][0]<<endl;}return 0;
}

HDOJ-1087 Super Jumping! Jumping! Jumping!

题目

有一种跳棋游戏，棋子在棋盘上呈线性排列。除起点与终点外，每个棋子上都标着一个正整数。玩家必须从起点跳到终点，在途中可以访问棋子，但每次只能向前访问更大的棋子，也可以不访问棋子。玩家在途中访问的棋子的数值之和就是最终得分。求最大得分。

思路

描述最优子结构： 该问题（找出从1出发能得到的最大和）的最优解包含了子问题（找出从1右边的点出发能得到的最大和）的一个最优解。
利用子问题的最优解来构造原问题的一个最优解：
递归公式：设data[i]为第i个棋子的数值，则
dp[i]= data[i]+maxi<j≤ndp[j]
递归定义最优解的值： dp[i]的每一个值仅依赖于dp[j]（i<j≤n）的值。通过以递增i的顺序来计算。

程序

#include<iostream>
using namespace std;
int max(int a,int b){if(a>b) return a;return b;}
int main(){int n,i,j,mdp;	while(cin>>n&&n){int data[1005]={0};//data存储各棋子数值，由于要用于判断，所以不能被和覆盖int dp[1005]={0};//dp[i]表示从i出发能得到的最大和		for(i=1;i<=n;i++)cin>>data[i];for(i=n;i>=0;i--){//最小从0出发mdp=0;for(j=i+1;j<=n;j++)//查找从i出发能走到的格子if(data[j]>data[i])mdp=max(mdp,dp[j]);dp[i]=data[i]+mdp;//dp[i]=走到i得分+从下一步出发能得到的最大和}cout<<dp[0]<<endl;//dp[0]为最终解}return 0;
}

【注】由于起点与终点具有对称性，从终点跳到起点得分是相同的，可以从前往后递推。

HDOJ-1176 免费馅饼

题目

有一天gameboy正走在回家的小径上，忽然天上掉下大把的馅饼。将小径视为数轴上一条线段，最小值为0，最大值为10，馅饼都掉在线段上的整数点，gameboy只能在线段上移动，0秒时他处于整数5的位置，每秒钟最多移动1米。求他最多可以接到的馅饼个数。

思路

本问题可画出与2084 数塔类似的塔状结构，表示玩家移动的路径。
易发现其与原始数塔的不同之处：多了辐射方向，第7层（第6秒）开始，层宽度不再增加。
描述最优子结构： 该问题（找出在第0秒从5出发的最大路线）的最优解包含了子问题（找出在第0秒从与5相邻的点出发的最大路线）的一个最优解。因此，在第0秒从顶点5出发的最大路线只能是三者之一：从顶点出发走到4，走在第1秒从4出发的最大路线；在5停留1秒，走在第1秒从5出发的最大路线；从顶点出发走到6，走在第1秒从6出发的最大路线。
利用子问题的最优解来构造原问题的一个最优解： 在求解状态（i,j）之前，dp[i][j] 存储第i秒在j位置落下的馅饼总数，求解之后表示第i秒从j出发得到的最大值。
递归公式：设tm为馅饼落下的最晚时刻，
i=tm时，dp[i][j]=dp[i][j]+0;
0<i<tm时，dp[i][j]=dp[i][j]+
$$\{\begin{array}{r}max(dp[i+1][0],dp[i+1][1])，j=0\\ max(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1])，1\le j\le 9\\ max2(dp[i+1][9],dp[i+1][10]),j=10\end{array}$$
以资源换代码复杂度： 从数塔可以看出，在6层以上，某些状态是没有意义的，如（4 的顺序来计算。

代码

#include<cstdio>
#include<cstring>
int dp[100005][11];//输入时，dp[t][p]表示第t秒在p位置落下的馅饼总数
//处理时，dp[i][j]表示第i秒从第j个位置开始的最优解
int max2(int a,int b){if(a>b) return a;return b;}
int max3(int a,int b,int c){if(a>=b&&a>=c) return a;if(b>=a&&b>=c) return b;return c;}
int main(){int n;while(scanf("%d",&n)&&n){int i,j;memset(dp,0,sizeof(dp));int t,p,tm=1;//tm代表最大时刻for(i=0;i<n;i++){scanf("%d%d",&p,&t);//题目坑点if(t>tm) tm=t;dp[t][p]++;}for(i=tm-1;i>=0;i--){//各时刻dp[i][0]+=max2(dp[i+1][0],dp[i+1][1]);for(j=1;j<=9;j++)//各位置dp[i][j]+=max3(dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1]);//这一秒状态由下一秒状态而来，这一秒位置只能是上一秒位置或其左右dp[i][10]+=max2(dp[i+1][9],dp[i+1][10]);}printf("%d\n",dp[0][5]);}return 0;
}

HDOJ-2602 Bone Collector

题目

有一个骨头收藏家带着一个容积为V的背包来到墓地收集骨头，每个骨头体积不同，价值也不同，求他能带走的骨头的价值总和的最大值。

思路

01背包原题
**最优子结构：**该问题（确定i个物品装到容积为j的背包产生的最大价值）的最优解包含了子问题（确定i-1个物品装到容积为j的背包产生的最大价值）的一个最优解。证明：令dp[i][j]表示i个物品装到容积为j的背包产生的最大价值。从i-1到i，多了一种骨头可供选择，可选择替换或不替换背包中原有的一个。若不替换，则dp[i][j]=dp[i-1][j]，dp[i-1][j]必须是最优的；若替换，须保证替换后取得更优解，则dp[i-1][j]必须是最优的。从j-1到j，背包容积增加1，可选择替换或不替换背包中原有的一个。若不替换，则dp[i][j]=dp[i-1][j]，dp[i-1][j]必须是最优的；若替换，须保证替换后取得更优解，则dp[i-1][j]必须是最优的。
利用子问题的最优解来构造原问题的一个最优解： 把问题转化为一个子问题和在子问题基础上做出的决策。在必须进行替换的情况下，最小代价是背包腾出新物品所需空间。至于为什么是dp[i-1][j-vo[i]]而不是dp[i][j-vo[i]]，是因为dp[i][j-vo[i]]考虑了物品i。
**递归定义最优解的值：**选择在状态（i,j）下的最优解的问题作为子问题，物品数量i=1,2,…,n。背包容积j=0,1,2,…,v。
我们的最终目标是确定在状态（n,v）下的最优解。当i=0时，dp[i][j]=0。递归公式：
$$\{\begin{array}{r}0，i=0\\ max(dp[i-1][j],dp[i-1][j-vo[i]]+va[i]),i\ge 1\end{array}$$
对于i>=1，dp[i][j]的每一个值仅依赖于dp[i-1][j]和dp[i-1][j-vo[i]]的值。因此，先有dp[i-1][x]后有dp[i][x]，通过以递增i的顺序来计算dp[i][j]的值，j的值变化顺序任意。
空间复杂度优化：新计算出的dp[i][x]可以直接覆盖dp[i-1][x]，则dp[j]=
$$\{\begin{array}{r}0，i=0\\ max(dp[j],dp[j-vo[i]]+va[i]),i\ge 1\end{array}$$
在计算dp[j]的时候需要引用dp[j-vo[i]]的值，因此以递减j的顺序来计算dp[j]的值，以避免dp[j-vo[i]]在被引用之前变化。

贪心解法错误的原因：对象量子性。由于对象不可分割，所以背包不一定装满。

代码

#include<iostream>
using namespace std;
int max(int a,int b){if(a>b) return a;return b;}
int main(){int t;cin>>t;while(t--){int n,v,i,j,va[1005]={0},vo[1005]={0},dp[1005]={0};cin>>n>>v;for(i=1;i<=n;i++) cin>>va[i];//va存储物品价值for(i=1;i<=n;i++) cin>>vo[i];//vo存储物品体积for(i=1;i<=n;i++)//i代表物品数量（从1到n）for(j=v;j>=0;j--){//j代表背包容积（从0到v）if(j>=vo[i]&&dp[j-vo[i]]+va[i]>dp[j]) dp[j]=dp[j-vo[i]]+va[i];//计算背包前一容积腾出第i个物品体积的情况下取得的最大价值与第i个物品价值之和}cout<<dp[v]<<endl;}return 0;
}

HDOJ-1421 搬寝室

题目

从n件物品中选2*k件搬到另一个地方，每次搬一对。现定义一次搬运产生的疲劳度为这对物品的重量之差的平方。给定k及其他数据，求完成所有搬运任务后累计的疲劳度的最低值。

思路

可以证明，当每次提的物品重量相邻时，疲劳度最小。因此，首先对输入数据进行排序。

描述最优子结构： 该问题（在前i个物品中选择j对的最低疲劳度）的最优解包含了子问题（在前i-1个物品中选择j对的最低疲劳度 与 在前i-2个物品中选择j-1对的最低疲劳度）的一个最优解。证明：令dp[i][j]表示在前i个物品中选择j对的最低疲劳度。从i-1到i，多了一种物品可供选择，可选择替换或不替换原有的一对。若不替换，则dp[i][j]=dp[i-1][j]，dp[i-1][j]必须是最优的；若替换，须保证替换后取得更优解，则dp[i-2][j-1]必须是最优的。
利用子问题的最优解来构造原问题的一个最优解： 一般来说，i每增加2，j的最大取值便可增加1。由于j的最大取值会变化，将dp[i][j](j*2>i)记为无穷大，表示不可用。

递归公式：设m[i]为排序后第i个物品的重量，
$$dp[i][j]=\{\begin{array}{r}0，i=0或j=0\\ min(dp[i-1][j],dp[i-2][j-1]+(m[i-1]-m[i]{)}^2),i\ge 2\end{array}$$

递归定义最优解的值：dp[i][j]的每一个值仅依赖于dp[i+1][j-1],dp[i+1][j],dp[i+1][j+1]的值。通过以递增i的顺序来计算。

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[2005][1005];//dp[i][j]表示在前i个物品中选择j对的最低疲劳度
#define INF 32768000
bool cmp(int x,int y){return x<y;}
int min(int x,int y){return x<y?x:y;}
int main(){int n,k,i,j;while(scanf("%d%d",&n,&k)!=EOF){int m[2005]={0};for(i=1;i<=n;i++)cin>>m[i];		sort(m+1,m+1+n,cmp);for(j=0;j<=k;j++)dp[0][j]=0;//第0行保留为0，使得第2行可以选择1对物品for(i=1;i<=n;i++)for(j=1;j<=k;j++)dp[i][j]=INF;//dp[i][j]初始化为无穷大，使得以后可以新增for(i=2;i<=n;i++)for(j=1;j*2<=i;j++)dp[i][j]=min(dp[i-1][j],dp[i-2][j-1]+(m[i-1]-m[i])*(m[i-1]-m[i]));cout<<dp[n][k]<<endl;}return 0;
}

HDOJ-1069 Monkey and Banana

题目

给出一些砖块，堆叠砖块建塔。砖块有n种类型，每种类型数量不限，形状为长方体，且可以改变放置方向。如果上层砖块的长、宽必须小于下层砖块的长、宽，求塔的最大高度。

思路

而本问题则要求满足塔中面积相邻的两块砖之前满足一定关系，即上层砖比下层砖小。因此，最好先进行排序，按顺序进行建塔。然而，排序的操作对象只能是有限个数量。在这里要看出陷阱：同一类型、同一摆放位置的砖块只能使用一次。1种砖块有3个维度，对应6种摆放方式，等效看成6种砖。注意，本题中与问题有关的参数是子问题空间，与01背包中允许选择的物品数量类似。

最优子结构： 将1→6扩充后的各砖块先按长度，后按宽度进行排序。问题（前i个砖能构成的塔的最大高度）的最优解包含了子问题（前j（j<i）个砖能构成的塔的最大高度）的一个最优解。为什么是j而不是i-1：排序具有的两个标准是有优先级别区别的，并不能保证前一个的长、宽均比后一个大。证明：令dp[i]表示前i个砖能构成的塔的最大高度。对于任意前j（j<i）个砖能构成的塔，有且仅有两种情况：第i块砖可以放到顶层或不可以。如果可以，则对应的前j（j<i）个砖能构成的塔的高度必须是最大的。
利用子问题的最优解来构造原问题的一个最优解： 把问题涉及到一个子问题，该子问题需要在所有j<i的选择中选出最优。
递归定义最优解的值： 选择在状态（i）下的最优解的问题作为子问题，子问题空间i=1,2,…,len。（len为砖块总数）。注意dp[i]不一定是递增的，所以我们的最终目标是确定所有状态下的最优的解。

递归公式：
dp[i]=h[i]+max(0,dp[j]) (1<=j<i且a[i]<[j]且b[i]<b[j])
dp[i]的每一个值仅依赖于dp[j]的值。因此，通过以递增i的顺序来计算dp[i]的值。

代码

#include<iostream>
#include<algorithm>
using namespace std;
int max(int a,int b){if(a>b) return a;return b;}
struct node{int x;int y;int z;}nd[185];
bool cmp(node a,node b){if(a.x!=b.x) return a.x>b.x;//先比较areturn a.y>b.y;}//后比较b
int main(){int n,i,j,t=0;while(cin>>n&&n){int len=1;//len代表数组长度for(i=0;i<n;i++){int a,b,c;cin>>a>>b>>c;//3个数6种排列nd[len].x=a;nd[len].y=b;nd[len].z=c;nd[len+1].x=a;nd[len+1].y=c;nd[len+1].z=b;nd[len+2].x=b;nd[len+2].y=a;nd[len+2].z=c;nd[len+3].x=b;nd[len+3].y=c;nd[len+3].z=a;nd[len+4].x=c;nd[len+4].y=a;nd[len+4].z=b;nd[len+5].x=c;nd[len+5].y=b;nd[len+5].z=a;len+=6;}sort(nd+1,1+nd+len,cmp);int dp[185]={0};int imax=0,jmax;//imax存储最高塔的高度for(i=1;i<len;i++){jmax=0;//jmax存储在i之前最高塔的高度for(j=1;j<i;j++){				if(nd[j].x>nd[i].x&&nd[j].y>nd[i].y)jmax=max(jmax,dp[j]);}dp[i]=nd[i].z+jmax;imax=max(imax,dp[i]);}cout<<"Case "<<++t<<": maximum height = "<<imax<<endl;}return 0;
}

USACO 2006 November Silver - Bad Hair Day

题目

n头奶牛站成一列(1≤n≤80000)，一只奶牛a可以看到前面比它矮的奶牛，但不能看到比它高或等的奶牛b及b之后的奶牛。输入奶牛的高度，输出每只奶牛可以看到的奶牛数量之和。

思路

奶牛的高度形成一个数列。
“俯视序列”：对于给定的i<j<=n+1，对于任意的i<k<j，有h[k]<h[i]，则称从i到j构成了一个“俯视序列”。
题目要求的就是i（1<=i<=n）的俯视序列的最大值之和。
i的俯视序列的最大值c[i]具有最优子结构：如果后面的牛i比前面j高，那么前面能看到的后面也能看到。最大俯视序列一直到比i高的牛为止。如果前面的牛能看到底，c[i]=c[j]+1；如果只能看到一部分，那么求出j的最大俯视序列，从该序列末尾后一个继续判断，c[i]为所有最大俯视序列之和。

代码

#include<iostream>
using namespace std;
const int N = 8e4 + 5; 
int main(){int n,h[N],c[N];int hm[N];//hm[i]看到的第一只比i高的牛的编号cin >> n;for(int i = 1; i <= n; i++) cin >> h[i];c[n]= 0;hm[n]= -1;//h[m]为-1代表没有牛比i高long long sum=0;for(int i = n-1; i >= 1; i--){ //从前往后遍历每只奶牛bool can = true;//can不仅仅代表是否能看到，而是结果是否产生 c[i] = 0;for(int j = i+1; can;){ //对于每只奶牛，从后往前逐只看if(h[i] <= h[j]){ //比我高，看不见 can = false;hm[i] = j;sum += c[i];}else{if(hm[j] == -1){ //j是j~n中最高的hm[i] = -1;c[i] += c[j] + 1;sum += c[i];can = false;} else{c[i] += c[j] + 1;j = hm[j];}}}}cout<<sum<<endl;return 0;
}

HDOJ-1160 FatMouse’s Speed

题目

输入包含多组数据，每组为一个老鼠序列，包含每只老鼠的体重与速度信息，输出长度最大的序列的长度及老鼠编号（其在原序列中出现的顺序），满足体重递增、速度递减。

思路

将输入数据首先按体重递增排序，其次按速度递减排序，这样，按顺序遍历各老鼠时，体重递增的要求自动满足。题目可抽象为寻找一个最长递减子序列。
考虑到子序列中的元素是离散分布在原系列当中的，题目又要求输出序列元素，可采取链表式的结构存储信息。一个结点中有2个成员，len表示子串最大长度，next表示下一项编号，将一项添加到链表末尾称为“连接”，其操作为：记该项的len为末项len+1，该项的next为末项编号。
dp[i].len=1+0,m[i].s>m[i+1].s1+maxi+1<j≤ndpj.len,mi.s≤m[i+1].s

代码

#include<cstdio>
#include<algorithm>
using namespace std;
struct mice
{int w;int s;int num;}m[1005];
bool cmp(mice x,mice y){if(x.w!=y.w) return x.w<y.w;//体重递增排序return x.s>y.s;}//速度递减排序
int main(){int n=1;while(scanf("%d%d",&m[n].w,&m[n].s)!=EOF){m[n].num=n;n++;}n-=1;sort(m+1,m+1+n,cmp);int i,j,sm=1,len=1,lenm=1;struct dongp{int len,next;}dp[1005]={0};//dp[i]存储从m[i]开始的子串的有关信息for(i=1;i<=n;i++){dp[i].len=1;dp[i].next=9999;}for(i=n-1;i>=0;i--){//从后往前遍历 if(m[i].s>m[i+1].s){//当前项比后一项大if(dp[i+1].len==1){//序列刚开始//将dp[i+1]与max(dp[j])(i+1<j<=n)连接 int lenm2=0;for(j=i+2;j<=n;j++){if(m[j].s<m[i+1].s&&dp[j].len>lenm2){lenm2=dp[j].len;dp[i+1].next=j;}					}dp[i+1].len+=lenm2;}//将dp[i]与dp[i+1]连接，用到更新后的dp[i+1]dp[i].next=i+1;dp[i].len=dp[i+1].len+1;}//序列结束，更新最长子序列 else if(dp[i+1].len>lenm){lenm=dp[i+1].len;sm=i+1;}}printf("%d\n",lenm);int ele=sm;	do{printf("%d\n",m[ele].num);ele=dp[ele].next;}while(ele!=9999);return 0;
}

HDOJ-1159 Common Subsequence

题目

给定一个序列X=<x1，x2，…，xm>，定义其子序列为原序列中去掉一个或多个元素，剩余元素保持先后顺序形成的序列。给定两个序列X和Y，求X和Y的最长公共子序列的长度。

思路

LCS的最优子结构
设X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>为两个序列，并设Z=<z1,z2,…,zk>为X和Y的任意一个LCS。
1）如果x[m]=y[n]，那么z[k]=x[m]=y[n]而且Z(k-1)是X(m-1)和Y(n-1)的一个LCS。
2）如果x[m]≠y[n]且z[k]≠x[m]，那么Z是X(m-1)和Y的一个LCS。
3）如果x[m]≠y[n]且z[k]≠y[n]，那么Z是X和Y(n-1)的一个LCS。
两个维度：序列X的长度和序列Y的长度。
一个递归解
在找X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的一个LCS时，可能要涉及一个或两个子问题。如果x[m]=y[n]，那么必须找出X(m-1)和Y(n-1)的一个LCS。如果x[m]≠y[n]，就必须解决两个子问题：找出X(m-1)和Y的一个LCS，以及找出X和Y(n-1)的一个LCS。这两个LCS中，较长的就是X和Y的一个LCS。问题具有重叠子问题性质：为找出X和Y的一个LCS，可能需要找出X(m-1)和Y的一个LCS以及X和Y(n-1)的一个LCS，而这两个问题都包含着找X(m-1)和Y(n-1)的一个LCS的子子问题。
定义c[i,j]为序列X(i)和Y(j)的一个LCS的长度。
c[i][j]=0,i=0或j=0ci-1,j-1+1,i>0且j>0且xi=y[j]max⁡(ci,j-1,ci-1,j),i>0且j>0且xi≠y[j]

参考代码

#include <stdio.h>
#include <string.h>
#define SIZE 1001
#define max(a,b) ((a)>(b)?(a):(b))
int dp[SIZE][SIZE];
char a[SIZE],b[SIZE];
int main(){while(scanf("%s%s",&a,&b)!=EOF){memset(dp,0,sizeof(dp));int lena=strlen(a);int lenb=strlen(b);for(int i=0;i<lena;i++)for(int j=0;j<lenb;j++)if(a[i]==b[j]) dp[i+1][j+1]=dp[i][j]+1;else dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);}printf("%d\n",dp[lena][lenb]);return 0;
}

总结

不要妄想一步登天。“子序列”本身也是一种数据集合，因此其可能存在最优子结构。不要一开始就想着解的最优子结构。
善用代数工具，学会抽象定义：两个序列的最长子序列也是序列

HDOJ-1058 Humble Numbers

题目

如果一个数的因数只有2，3，5，7（含它们的倍数），则称这个数为丑数。输入正整数n（1 <= n <= 5842），输出第n个丑数的值。

思路

第一个丑数为“1”，后面的每一个丑数都是由已经生成的丑数乘2、3、5或7而来，那么后一个丑数就是已经生成的丑数乘2、3、5或7得到的最小值
第一个：1
第二个：1*2,1*3,1*5或1*7中最小为2，2已乘过第1个丑数，更新为2与第2个丑数相乘
第三个：2*2,1*3,1*5或1*7中最小为3，3已乘过第1个丑数，更新为3与第2个丑数相乘
第四个：2*2,2*3,1*5或1*7中最小为4，2已乘过第2个丑数，更新为2与第3个丑数相乘
……

参考代码

# include<stdio.h>
# define MAX 5842
__int64 num[MAX+1];
__int64 min(__int64 a,__int64 b,__int64 c,__int64 d){__int64 min1,min2;min1=a<b?a:b;min2=c<d?c:d;if(min1<=min2) return min1;else return min2;
}
int main(){int i=1,n;num[1]=1;int p2,p3,p5,p7;p2=p3=p5=p7=1;//p2,p3,p5,p7分别代表2，3，5，7乘的丑数序号while(i<MAX){num[++i]=min(num[p2]*2,num[p3]*3,num[p5]*5,num[p7]*7);if(num[i]==num[p2]*2) p2++;if(num[i]==num[p3]*3) p3++;if(num[i]==num[p5]*5) p5++;if(num[i]==num[p7]*7) p7++;}while(scanf("%d",&n)!=EOF){if(n==0) break;else{if(n%10==1&&n%100!=11)//eleventhprintf("The %dst humble number is %lld.\n",n,num[n]);else if(n%10==2&&n%100!=12)//twelfthprintf("The %dnd humble number is %lld.\n",n,num[n]);else if(n%10==3&&n%100!=13)//thirteenthprintf("The %drd humble number is %lld.\n",n,num[n]);else printf("The %dth humble number is %lld.\n",n,num[n]);}}return 0;
}