选修课专业知识市公开课金奖市赛课一等奖课件

ACM程序设计基础第1页主流算法：1.搜索//回溯2.DP（动态规划）3.贪心4.图论//Dijkstra、最小生成树、网络流5.数论//解模线性方程6.计算几何//凸壳、同等安置矩形并面积与周长7.组合数学//Polya定理8.模拟9.数据结构//并查集、堆10.博弈论第2页2.1回溯法需要用计算机求解组合试题普通有两种类型：1．能够用简明正确组合公式揭示问题。*尽可能用解析法求解。2．不能对给定问题建立数学模型，或即便有数学模型但解该模型准确方法也不一定能利用现成算法。在求解枚举类型试题时,常会碰到这类问题。*普通采取搜索方法处理，即从初始状态出发，利用题目给出条件、规则扩展全部可能情况，从中找出满足题意要求解答。第3页回溯法：该方法首先暂时放弃关于问题规模大小限制，并将问题候选解按某种次序逐一枚举和检验。

当发觉当前候选解不可能是解时，就选择下一个候选解；

若当前候选解除了还不满足问题规模要求外，满足全部其它要求时，继续扩大当前候选解规模，并继续试探。

假如当前候选解满足包含问题规模在内全部要求时，该候选解就是问题一个解。

定义:在回溯法中，放弃当前候选解，寻找下一个候选解过程称为回溯。扩大当前候选解规模，以继续试探过程称为向前试探。第4页回溯法基本思想：确定了解空间组织将结构后，回溯法就从开始结点（根结点）出发，以深度优先方式搜索整个解空间。这个开始结点就成为了一个“活结点”，同时也成为当前扩展结点。在当前扩展结点处，搜索向纵深方向移到一个新结点。这个新结点就成为一个新活结点，并成为当前扩展结点。假如在当前扩展结点处不能再向纵深方向移动，则当前扩展结点就成为“死结点”。此时，应往回移动（回溯）至最近一个活结点处，并使这个活结点成为当前扩展结点。第5页回溯法解题步骤：针对所给问题，定义问题解空间确定易于搜索解空间结构以深度优先方式搜索解空间，而且在搜索过程中有剪枝函数防止无效搜索第6页[例1]N皇后问题

一个n×n国际象棋棋盘上放置n个皇后，使其不能相互攻击，即任何两个皇后都不能处于棋盘同一行、同一列、同一条斜线上，试问共有多少种摆法?第7页一、怎样求M皇后问题

几个惯用概念：

1．状态(state)

状态是指问题求解过程中每一步情况。n皇后问题中，某行皇后所在列位置i(1＜=i＜=n)即为其时皇后问题状态。显然，对问题状态描述，应与待处理问题自然特征相同，而且应尽可能做到占用空间少，又易于用算符对状态进行运算。第8页2．算符(operater)

算符是把问题从一个状态变换到另一个状态方法代号。算符通常采取适当数据来表示。N皇后一个摆法对应1．．n排列方案(a1，…，an)。排列中每个元素ai对应i行上皇后列位置(1＜=i＜=n)。由此想到，在n皇后问题中，可采取当前行列位置i(1＜=i＜=n)作为算符。因为每行仅放一个皇后，所以行攻击问题不存在，但在试放当前行一个皇后时，不是全部列位置都适用。第9页例假如(L，i)位置放一个皇后，若与前1．．L-1行中j行皇后产生对角线攻击(abs(L-j)=abs(j行皇后列位置-i))或者列攻击(i＝j行皇后列位置)，那么算符i显然不适用，应该舍去。所以，不产生对角线攻击和列攻击是n皇后问题约束条件，即排列(排列a1，，…，ai，…，ai，…，an)必须满足条件(|j-i|≠|aj-ai|)and(i≠aj)(1＜=i，j＜=n)。第10页3．结点(node)

用以表明某状态特征及关联方式基本信息单元。结点数据结构普通为结构体类型。

现在先观察一个简单n皇后问题。设n＝4，初始状态显然是一个空棋盘。第11页第12页第13页第14页第15页第16页算符个数即为解答树次数。由图可见，4皇后解答树是4次树。

第17页

一棵树中某个分枝结点也可视作为“子根”，以此结点为根树则称作“子树”。由此能够看出解答树结构：

1．初始状态组成(主)树根结点；

2．除根结点以外，每个结点都含有一个、且只有一个父结点。对应于n皇后问题来说，置放i行皇后子结点，只有在置放了前i-1行皇后一个父结点基础上产生；

3．每个非根结点都有一条路径通往根结点，其路径长度(代价)定义为这条路径边数。对应于n皇以后说，当前行序号即为路径代价。当路径代价为n+1时，说明n个皇后已置放完成，一个成功摆法产生。第18页

有了以上基础知识和对n皇后问题初步分析，可知，求解n皇后问题，两个步骤：

1．从左至右逐条树枝地结构和检验解答树t；

2．检验t结点是否对应问题目标状态。

上述两件事同时进行。为了加紧检验速度，普通要求：

1．在扩展一个分枝结点前进行检验，只要它不满足约束条件，则不再结构以它为根子树；

2．已处理过结点若以后不会再用，则无须保留。即回溯过程中经过结点不再保留。第19页二、回溯法算法分析和程序框架

从左至右逐条树枝地结构和检验查找解答树，已处理过结点若以后不再使用则无须保留(通常，检验长度为n树枝，只要保留n个结点即可)。

若按此方式得到一条抵达树叶树枝t，实际上就得到一条路径，然后沿树枝t回溯到第一个还未使用过通往右边路径方向上分枝点，并由此分枝点向右走一步，然后再从左至右地逐一进行结构和检验，直至抵达叶子为止，这时又得到一条路径。照此搜索下去，直至求出全部路径。显然用此法检验，在树枝左边一切结点都已检验过，树枝右边一切结点还未产生。这种不停“回溯”查找解答树中目标结点方法，即“回溯法”。第20页

由上述算法思想，轻易想到，应选择怎样一个数据结构来存放当前路径上各结点状态和算符?它应含有“后进先出”特征，这就是通常所说栈。为回溯法设计一个递归过程arrange()，就是利用系统这一特征。第21页

1．在全局变量说明中，分配一个连续数组区域stack[maxdepth]，次序存放栈中表目，即当前路径结点。栈元素为结点，普通用路径最大长度maxdepth作为栈容量，直接用当前数组下标L指向栈顶，但L不允许是全局变量。

2．栈顶指针L作递归程序arrange值参数，指出待扩展结点在当前路径序列stack中次序，算符作arrange函数局部变量。第22页3．递归过程边界条件是：

(1)若stack[L]是目标结点；

(2)若stack[L]再无可使用算符，即无法再扩展。4．只要当前结点能扩展，则递归调用arrange（L+1）。5．主程序中调用arrange(1)，从初始结点出发回溯搜索。递归结束返回主程序时(此时L恢复为1)表明全部路径搜索完成。第23页算法设计：用（k，j）表示棋盘位置，k为列号，j为行号。显然，每一列都必须有且只有一个皇后。所以，从第一列开始，从左向右依次放置8个皇后。开始棋盘为空，对于第1个皇后（k=1）可试探行号从1到8全部位置。设第1个皇后放置行号为n1，则第2个皇后（k=2）从1到8测试每个行号是否与第1列皇后（1，n1）相冲突，选择一个与皇后（1，n1）不冲突位置（2，n2），然后试探第3个皇后位置（3，n3），如此试探下去，直到放置好第8个皇后。试探过程中，假如第k个皇后已无位置可放，则退回前一列，试探第k-1个皇后下一个可放置位置。假如第k-1个皇后也没有可放置位置，则再退一列，试探第k-2个皇后下一个可放置位置。这么一直回溯到第1列，假如第1个皇后已试完最终一个行号8则算法应该停顿。第24页

试探第k个皇后可放置位置时，必须考虑前面k-1列皇后位置，假如位置（k，j）不与（1，n1），（2，n2）…（k-1，nk-1）位置上皇后冲突，则位置（k，j）可用于放置第k个皇后。位置（k，j）与位置（i，ni）关系如图：其中k>i，i=1，2，…，k-1；第25页

Qk-i=j-ni（i，ni）ni=jk-i=ni-j12345678列号行号87654321第26页

位置（k，j）与位置（i，ni）不能在同一列：必须ni！=j；位置（k，j）不能在位置（i，ni）发出向上45度斜线上：必须k-i！=j-ni；位置（k，j）不能在位置（i，ni）发出向下45度斜线上：必须k-i！=ni-j；所以，假如ni==j||（k-i）==abs（ni-j），则位置（k，j）不能放置皇后。显然，当i=1，2，…，k-1时，任何一个（i，ni）与（k，j）冲突，位置（k，j）都不能放置皇后。第27页introw[9];

voidarrange(intk)

{inti,j;

if(k>8)

{for(i=1;i<=8;i++)printf("%2d",row[i]);

printf("\n");return;

}

for(j=1;j<=8;j++)

{for(i=1;i<k;i++)if(row[i]==j||(k-i)==abs(row[i]-j))break;

if(i>=k)

{row[k]=j;

arrange(k+1);

}}}依次试探约束条件voidmain()

{arrange(1);}第28页

另外，因为回溯包括到变量保留，所以，在有情况下，用位运算可方便中间变量保留。

》》》queen2.cpp例题第29页例题：P2078Givenann*nmatrixA,whoseentriesAi,jareintegernumbers(0<=i<n,0<=j<n).AnoperationSHIFTatrowi(0<=i<n)willmovetheintegersintherowonepositionright,andtherightmostintegerwillwraparoundtotheleftmostcolumn.YoucandotheSHIFToperationatarbitraryrow,andasmanytimesasyoulike.Yourtaskistominimize第30页题意：给一个n*n数组，数组元素都为整数，数组每行能够循环右移，每次循环移动后，把每列元素加起来所得结果中找出一个最大值，每次循环移动后都能够得到一个最大值，在这全部最大值中找出最小结果输出。如有数组：123456789第31页下面是该数组求解过程：max：181716171615161517在全部得到max中找出最小值：15。最终输出15。第32页算法描述：采取回溯法，依次找出全部最大值，再找出全部最大值中最小值输出。循环移动一位代码以下：voidtrans(introw)//平移数组一行{inti,t=a[row][n];for(i=n;i>=2;i--){a[row][i]=a[row][i-1];}a[row][1]=t;}采取回溯法，能够让第一行保持不变，让其它行移动。采取递归实现。首先要找到递归返回条件，这里是当循环到最底层时候返回，也就是把123作为第一层k=1，456作为第2层k=2，789作为第3层k=3。当k=3时，找出此时数组中各列和中最大值，假如比min小，则min=max。这段代码为：第33页if(k>=n){//得出平移一次后最大值

max=0;for(j=1;j<=n;j++){sum=0;for(i=1;i<=n;i++){sum+=a[i][j];}if(sum>max)max=sum;}if(min>max)min=max;//假如这个最大值小于现在最小值，则给min赋值

return;}第34页for(i=1;i<=n;i++){//要平移次数

get(k+1);if(k==0)return;trans(k+1);}而每行要平移次数为n，所以每行要平移n次，假如k==0时候返回到主函数。因为第一行不用平移。上面算法所得程序代码总为：第35页#include"stdio.h"intn,min,max;inta[8][8];voidtrans(introw)//平移数组中一行{inti,t=a[row][n];for(i=n;i>=2;i--){a[row][i]=a[row][i-1];}a[row][1]=t;}voidget(intk){inti,j,sum;if(k>=n){//得出平移一次后最大值max=0;for(j=1;j<=n;j++){sum=0;for(i=1;i<=n;i++){sum+=a[i][j];}if(sum>max)max=sum;}if(min>max)min=max;return;}for(i=1;i<=n;i++){//要平移次数

get(k+1);if(k==0)return;trans(k+1);}return;}第36页intmain(){inti,j;scanf("%d",&n);while(n!=-1){min=100000;for(i=0;i<8;i++)for(j=0;j<8;j++)a[i][j]=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++){scanf("%d",&a[i][j]);}get(0);printf("%d\n",min);scanf("%d",&n);}return0;}第37页

由上述解题过程能够看出，有了回溯法算法框架，搜索一条路径或全部路径程序就比较清楚了。但这仅是在普通情况下。若求解过程出现下述情况：

1．求满足某个特定条件一条最正确路径；

2．扩展结点时参加运算变量有多个，组成多元化约束条件；

3．需对当前状态分情形进行递归搜索。

就不能简单套用回溯法算法框架了，必须详细问题详细分析。第38页练习北大：1011Sticks1020AnniversaryCake1072PuzzleOut1055BULKMAILING第39页2.2贪心法贪心法也是从问题某一个初始解出发，向给定目标递推。但不一样是．推进每一步不是依据某一固定递推式，而是做一个当初看似最正确贪心选择，不停地将问题实例归纳为更小相同子问题，并期望经过所做局部最优选择产生出一个全局最优解。

问题是：这种局部贪心选择是否能够得出全局最优解呢?在一些情况下是能够。第40页[例1]删数问题

键盘输入一个高精度正整数N，去掉其中任意s个数字后剩下数字按原左右次序组成一个新正整数。编程对给定N和S，寻找一个方案使得剩下数字组成新数最小。输出应包含所去掉数字位置和组成新正整数。(N不超出240位)输入数据均不需判错。第41页

算法分析：首先必须注意，试题中正整数N有效位数为240位，而计算机中整数有效位(包含符号位)不过11位，不论怎样也达不到试题数值要求。所以，必须采取可含256个字符字串来替换整数。以字串形式输入N，使用尽可能迫近目标贪心法来逐一删去其中S个数符，每一步总是选择一个使剩下数最小数符删去。之所以作出这么贪心选择，是因为删s个数符全局最优解．包含了删一个数符子问题最优解。第42页

为了确保删1个数符后数最小，我们按高位至低位方向搜索递减区间。若不存在递减区间，则删尾数符；不然删递减区间首字符，这么形成了一个新数串。然后回到串首，重复上述规则，删下一数符……依这类推，直至删除S个数符为止。第43页

比如：N＝’178543’．S＝4．删数过程以下：

N=‘178543’N=‘17543’N=‘1543’N=‘143’N=‘13’

显然，按上述规则删去s个数符后，剩下N-s个数符组成新数必定最小。下面是程序题解：第44页#include"stdio.h"#include"string.h"voidmain(){ints,i,j;charn[10],ch;printf("n=");scanf("%s",&n);printf("s=");scanf("%d",&s);第45页while(s>0){i=1;while(i<strlen(n)&&n[i]<=n[i+1])i++;for(j=i;j<strlen(n);j++)n[j]=n[j+1];s--;}while(strlen(n)>1&&n[0]=='0')for(j=0;j<strlen(n);j++)n[j]=n[j+1];printf("%s",n);}第46页

问题：对一个最优化问题，我们怎样才能知道它是否适合用于贪心算法求解？没有一个通用方法。但适合用于贪心策略求解大多数问题都有两个特点：

1．贪心选择性质——可经过做局部最优(贪心)选择来到达全局最优解贪心策略通常是自顶向下。第一步为一个贪心选择，将原问题变成一个相同、但规模更小问题．而后每一步都是当前看似最正确选择。这种选择可能依赖于已作出全部选择，但不依赖有待于做选择或子问题解。从求解全过程来看．每—次贪心选择都将当前问题归纳为更小相同子问题，而每一个选择都仅做一次，无重复回溯过程，所以贪心法有较高时间效率。第47页2．最优子结构——问题最优解包含了子问题最优解比如[例1]中，N＝’178543’．s＝4。第一步贪心选择为删’8’，即第一个子问题最优解为’8’；第二步贪心选择为删’7’，即第二个子问题(第一个子问题子问题)最优解为‘7’；继后第三个，第四个子问题最优解分别为’5’和’4’。很显然，问题最优解包含了四个子问题最优解，所以删数问题含有最优子结构性质。但问题是．对全部具备最优子结构问题是否都可采取贪心策略呢?不一定。下面，我们来考查一个经典优化问题两种变形。第48页[例2]背包问题

有一个贼在偷窃一家商店时发觉有N件物品：第i件物质值vi元，重Wi磅．(1<=i<=n)，此处vi和wi都是整数。他希望带走东西越值钱越好，但他背包中最多只能装下W磅东西(W为整数)。有两种偷窃方式：

1)0-1背包问题假如每件物品或被带走或被留下，小偷应该带走哪几件东西?2)部分背包问题假如允许小偷可带走某个物品一部分，小偷应该带走哪几件东西?每件东西重量是多少?第49页

算法分析：两种背包问题都含有最优化结构性质：对于0-1背包问题，考虑重量至多为W磅最值钱一包东西。假如我们从中去掉物品J，余下必须是窃贼从其余n-1件物品中可带走重量至多为W-Wj最值钱一件东西；假如我们再从中去掉物品i，余下也必须是窃贼从其余n-2件可带走、重量至多为W-Wj-Wi最值钱一件东西……，依次类推。对于部分背包问题，假如我们考虑从最优货物中去掉某物品J重量Wp（Wj>=Wp），则余下物品必须是窃贼能够从N-1件原有物品和物品JWj-WpJ中可带走、重量至多为W-Wp最值钱一件东西……，依次类推。第50页比如，总共有三件物品和一个背包。重量价值每磅价值物品1：10磅60元6物品2：20磅100元5物品3：30磅120元4背包：50磅按照一个贪心策略，窃贼开始时对含有最大每磅价值物品尽可能多拿一些。假如他拿完了该物品后仍能够取一些其它物品时，他就再取含有次大每磅价值物品，一直继续下去，直到不能取为止。第51页

若对0-1背包问题采取贪心策赂话．次序取物品1和2。不过从下列图能够看出，最优解取是物品2和3，没有取物品1。包含物品1可能解都不是最优解。物品330磅物品220磅背包价值120100背包价值12060物品330磅物品110磅第52页

在0-1背包问题中不应取物品1原因在于这么无法将背包填满，空余空间降低了它每磅价值．所以当我们考虑是否要把一件物品加到背包中时，必须对把加进该物品子问题解与不取该物品子问题解进行比较。由这种方式形成子问题造成了许多重迭子问题。对于这一类虽含有最优化结构性质、但产生子问题互为重迭试题，普通采取动态程序设计方法求解。第53页2.3动态规划

采取分治策略，把求最优解问题分解为求若干个子问题最优解，子问题也递归地分解为子问题组合，经过递归递推等方法，把原问题最优解与局部子问题最优解联络起来，以求最终解。第54页一、递归编程引例1

一个楼梯有20级，每次走1级或2级，从底走到顶一共有多少种走法？分析：设从底走到第n级走法有f(n)种，走到第n级有两个方法，一个是从第(n-1)级走1步，另一个是从第(n-2)级走2步，前者有f(n-1)种方法，后者有f(n-2)种方法，所以f(n)=f(n-1)+f(n-2)，另外，f(0)=1,f(1)=1.第55页程序：#include<iostream.h>intf(intn){if(n==0||n==1)return1;elsereturnf(n-1)+f(n-2);}voidmain(){cout<<f(20)<<endl;}第56页二、动态规划基本原理动态规划关键：发觉子问题和统计子问题。例1中，子问题就是：从底走到第n级走法有多少种，即f(n);子问题分析：1）对这些子问题可递归求解，即当n>1时，f(n)=f(n-1)+f(n-2)；不然，f(0)=1,f(1)=1.2)这些子问题是有重合，即求解某个问题时候，一些子问题可能需要求解屡次。当某个问题符合以上两点，就能够考虑用动态规划方式来高效求解。即：将子问题及其解统计下来，这么每个子问题只需求解一次，从而提升效率。第57页#include<iostream.h>intresult[100];//用于保留f(n)结果intf(intn)if(result[n]>=0)returnresult[n];//假如问题已被求解，那么直接返回结果intres;if(n==0||n==1)res=1;elseres=f(n-1)+f(n-2);result[n]=res;//计算解并将结果保留到result[n]中returnres;}解1（递归结构）第58页voidmain(){for(inti=0;i<=20;i++)result[i]=-1;//将全部结果先置为-1，表示还未求解cout<<f(20)<<endl;}第59页解2(递推结构）：#include<iostream.h>intf[100];voidmain(){f[0]=1;f[1]=1;for(inti=2;i<=20;i++){f[i]=f[i-1]+f[i-2];}cout<<f[20]<<endl;}第60页三、动态规划惯用技巧一）顺推先计算小子问题，然后再计算大子问题，最终把目标问题处理。顺推方法最关键一点就是当求解某个子问题时候，这个子问题需要用子问题都必须是已经被求解了，不然这个子问题计算结果就可能有误。第61页顺推思绪：

由题意(或递推关系)确定初始值F1(边界条件)；求出顺推关系式Fi＝g(Fi-1)；

i＝1；{由边界条件F1出发进行顺推}

while

当前结果Fi非最终止果Fn

do由Fi＝g(Fi-1)顺推后项；输出顺推结果Fn和顺推过程；第62页例2：一个城市街道布局如图，从最左下方走到最右上方，每次只能往上或往右走，一共有多少种走法？第63页分析:子问题为—从（0,0)走到（x,y），每次只能往上或往右走，一共多少种走法，将走法数记为f(x,y)，原问题就是求f(10,10).f(x,y)=f(x-1,y)+f(x,y-1)（x>0且y>0)f(x,y)=1(x=0或y=0）第64页程序：#include<iostream.h>intf[100][100];//保留结果voidmain(){inti,j;for(i=0;i<=10;i++){f[i][0]=1;f[0][i]=1}//置初始解

for(i=1;i<=10;i++)for(j=1;j<=10;j++)f[i][j]=f[i-1][j]+f[i][j-1];cout<<f[10][10]<<endl;}第65页二）递归实现

动态规划算法大多含有递归结构，所以用递归方法来实现动态规划算法往往更直接。即：增加一些内存单元来保留子问题解，在递归求解开始判断该子问题是否已经被求解过，若是，直接返回之前统计下来解，不然才递归求解，并在最终保留这个解，使得以后不用再求解相同问题。第66页例2解（递归方法实现动态规划）#include<iostream.h>intf[100][100];intgetf(intx,inty){if(f[x][y]!=-1)returnf[x][y];//判断是否已被求解，若是，则直接返回统计下解

intresult;if(x==0||y==0)result=1;elseresult=getf(x-1,y)+getf(x,y-1);f[x][y]=result;returnresult;//统计结果并返回}第67页voidmain(){intI,j;for(i=0;i<=10;i++)for(j=0;j<=10;j++)f[i][j]=-1;cout<<getf(10,10)<<endl;}第68页三）子问题编码

有时候子问题比较复杂，不轻易直接统计其解，能够考虑把子问题编号，然后把结果保留到一个数组里，即把第i个子问题解统计在数组第i个组员里。这个方法关键就是设计出一个函数把全部状态一对一映射到前面子问题编号中。第69页例：题目描述：给定M*N矩阵，其中每个元素都是-10到10之间整数。你任务是从左上角（1，1）走到右下角（M,N），每一步只能够向右或者向下，而且不能够走出矩阵范围。你所经过方格里面数字都必须被选取，请找出一条最适当道路，使得在路上被选取数字之和是尽可能小正整数。第70页分析：关键：要注意到每个数取值范围是-10到10之间，M和N最多也是10，所以，所取得数和最多为10×10×10=1000，最小为-10×10×10=-1000，所以能够利用这个有限性来定义子问题，详细分析以下：从左上角走到第x行第y列时，所取数和为d，这个状态可否到达？0<=x<=10,0<=y<=10,-1000<=d<=1000,所以状态数为11×11×，范围能够接收。第71页递归法求解各子问题：抵达（x,y)有两种情况，一个是从上方走下来，另一个是从左方走过来，若其中一个可达，则本状态可达。即：若“x>0且{x-1,y,d-a[x][y]}可达”或“y>0且{x,y-1,d-a[x][y]}可达”，则{x,y,d}可达。第72页#include<stdio.h>#include<string.h>intm,n;inta[10][10];charf[10][10][];boolsolve(intx,inty,intd){char&res=f[x][y][d+1000];if(res!=-1)returnres;//若已经求解，则直接返回结果

//递归求解

if(!x&&!y)returnres=(d==a[0][0]);if(x&&solve(x-1,y,d-a[x][y]))returnres=1;if(y&&solve(x,y-1,d-a[x][y]))returnres=1;returnres=0;}第73页intmain()

{

while(scanf(“%d%d”,&m,&n)==2)

{inti,j;

for(i=0;i<m;i++)

for(j=0;j<n;j++)scanf(“%d”,&a[i][j]);

//置为-1，表示没有被求解

memset(f,255,sizeof(f));

intans=-1;

for(i=1;i<=m*n*20;i++)//求最小可达正整数

if(solve(m-1,n-1,i))

{ans=i;break;}

printf(“%d\n”,ans);

}

return0;

}第74页435712-27-444-998输入：输出：11第75页四、设计动态规划法步骤：1、找出最优解性质，并刻画其结构特征；2、递归地定义最优值（写出动态规划方程）；3、以自底向上方式计算出最优值；4、依据计算最优值时得到信息，结构一个最优解。步骤1-3是动态规划算法基本步骤。在只需要求出最优值情形，步骤4能够省略，步骤3中统计信息也较少；若需要求出问题一个最优解，则必须执行步骤4，步骤3中统计信息必须足够多方便结构最优解。第76页动态规划问题特征：

动态规划算法有效性依赖于问题本身所含有两个主要性质：最优子结构性质和子问题重合性质。1、最优子结构：当问题最优解包含了其子问题最优解时，称该问题含有最优子结构性质。2、重合子问题：在用递归算法自顶向下解问题时，每次产生子问题并不总是新问题，有些子问题被重复计算屡次。正是利用了子问题重合性质，对每一个子问题只解一次，而后将其解保留在一个表格中，在以后尽可能多地利用这些子问题解。第77页练习：1010STAMPS1042GoneFishing1093FormattingText1050TotheMax1074ParallelExpectations第78页有些自然界和日常生活中事件，若用计算机极难建立