3、所以f3(a)=f3(a)=y，=—2-Vx2yja-x2^1x(a-x)所以nx=a-x,(n+l)x二a二JO+l)aax=—用数学归纳法可以证明：fn(a)二J臥,Xi=X2=X3=...=Xn=—n证明:1:n=l...2：设fn(a)=y[nci,xi=x2=X3=...=xn=—成立,nfn+i(a)=max(y[x+fn(a-x))=max(y[x+Jn(a—兀))令y=Vx+Jn(a一x)4n4a-x-4nx八=0我们刚才的解题策略是：“摸着石头过河”，f2利用fl的结果，f3又利用卫的结果。。。。。。类似于游戏屮的一个勇士打败了一些敌人后得到一件武器，然后去打败另
4、一个强大一些的对手，得到一件更好的武器，接着打败更强大的敌人ooooo最后取得胜利。。。在实际生活中，有这么一类问题，它们的活动过程可分为若干个阶段，而且在任一阶段后的行为仅依赖于第I阶段的过程状态，而与I阶段之前的过程如何达到这种过程如何达到这种状态的方式无关，这样的过程就构成了一个多阶段决策过程。在50年代，贝尔曼(RichardBellman)等人根据这类问题的多阶段决策的特性，提出了解决问题的“最优性原理”从而创建了最优化问题的一种最新的算法设计方法一一动态规划。分治法和动态规划法的比较动态规划算法与分治法类似，其根本思想也是将待求解问题分解成若干个子问题，先求解子问题，然
5、后从这些子问题的解得到原问题的解，与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是互相独立的.以从16个数据屮找出最大者为例,说明分治法的“静”和动态规划法的“动”的区别。下面我们以具体的例子來说明如何运用动态规划算法來求解问题，并分析可用动态规划算法解的问题的所应具备的一般特征。对教材68页上的里子给予简要说明(因为书上的文字叙述有些含混晦涩，对符号的说明不清晰)ya2K3P1S2UF下面精讲一个例子212232G3L4Q5TC34123DHMR22134A013231.介绍这个图的特点..…从而说明从0到A的最短路径必由7段而不是更多或更少段组成。其行
6、进路线必然是x和y单调递增的(非严格单调)。从0(0,0)到U(4,3)点的每一条路径对应于由4个x上的和3个y上的字符构成的字符串，这种字符串的数目为C；=35.如果采用穷举法进行搜索，需要进行35*6=210次加法，34次比较。2.下血我们采用动态规划法来解决这一问题。令O为起点到U的最短距离为Do,以A为起点到U的最短距离为Da・・■，用g表示(i,j)边的长度。显然Ds=dsu=2,Dt=dTU=3,Dq二min{2+2,5+3}=4Dp=l+Ds=1+2=3Dr=3+Dt=3+3=6Drmin{Dlq+DQ,du>+DP}=min{4+Dq,2+Dp}=min{4+4,2
7、+3}=5Dk=3+Dp=3+3=6Dm=min{2+Dq,4+Dr}=min{2+4,4+6}=6Dn=4+Dr二4+6=10D卜=2+Dk=2+6=8Do=min{1+Dk,3+Dl}=min{1+6,3+5}=7Dn=min{1+5,1+6}=6Dj=min{3+Dm»3+Dn}=min{3+6,3+10}=9Dc=min{2+Df,2+Dg)=min{2+&2+7}=9DD=min{4+Dg,2+Dh}二min{4+7,2+6)=8DE=min{1+DH,2+Dj}=min{1+6,2+9}二7DA=min{3+D(：,2+D°}=min{3+9,2+8}=10DB=min
8、{2+Dd,3+De}==min{2+8,3+7}=10Do==min{1+Db,2+Da}=min{1+10,2+10}二11共进行了29次加法，12次比较。由Do=l+DB=11回溯，可得到最短路径为O—>B・TD->H9L—>P-TS・TUOTBTETH—PTSTU推广到x轴m段y轴n段的情形：用动态规划法需要做2mn+(m+n-2)次加法，mm次比较；而如果用穷举法，需要(^+n)!*(m+/7-l)次加法，创+")!-1次比较。加〃！m!n!若动态规划法要做
