内容发布更新时间 : 2024/11/15 5:52:44星期一 下面是文章的全部内容请认真阅读。
动态规划算法：
引言：
动态规划算法是求解最有问题的一种高效率的算法。其使用的原则是优化原则，即整体的最优解可以通过局部的最优解获得。问题求解的过程可以概括成两句话：自顶向下的分析，自下向上的计算。矚慫润厲钐瘗睞枥庑赖賃軔朧。 典型例题
例1、数塔问题：设有一个三角形数塔，顶点节点称为根结点，每个节点有一个数值。从顶点出发，可以想左走也可以向右走。搜索从顶点出发向下走至塔底的所有路径中节点和最大的路径及最大和值。聞創沟燴鐺險爱氇谴净祸測樅。 问题分析：
1 选择最佳算法：
贪心算法----不能求最优解；
穷举算法----当塔层数很大时，计算量过大。 其它算法？
2 选择最佳数据结构表示数据： g[I,j,1]:表示为置[I,j]结点本身数值； g[I,j,2]:能取得的最大值；
g[I,j,3]:前进方向，0---向下；1—向右下。
源程序： program d1; const n=5; var i,j:integer;
g:array[1..n,1..n,1..3] of integer;
begin
for i:=1 to n do begin
for j:=1 to i do begin
read(g[i,j,1]);
g[i,j,2]:=g[i,j,1];g[i,j,3]:=0; end; readln; end;
for i:=n-1 downto 1 do for j:=1 to i do
if g[i+1,j,2]>g[i+1,j+1,2] then g[i,j,2]:=g[i,j,2]+g[i+1,j,2]
else begin g[i,j,2]:=g[i,j,2]+g[i+1,j+1,2]; g[i,j,3]:=1 end;
1 / 5
writeln('max:=',g[1,1,2]); write(g[1,1,1]); j:=1;
for i:=1 to n-1 do begin
j:=j+g[i,j,3];
write('-',g[i+1,j,1]:4); end;
writeln; end.
例2、求城市间最短通路问题：设有n个城市分布在一条干道上，相邻城市间由若干通路，每条通路上有一个数字表示通路的距离，如下图所示。求出A到E的最短距离。残骛楼諍锩瀨濟溆塹籟婭骒東。
B C D E A
例3、马的路径问题。在一个N*M的棋盘上的P点有一个中国象棋的马，而在棋盘的另一端有一个位置Q，约定P在Q的左端，试编程找出P至Q的所有路径条数。酽锕极額閉镇桧猪訣锥顧荭钯。 参考输入:
棋盘:6*6 P的位置（4，1）Q位置（3，6） 参考输出：8
参考程序: program horse;
var a:array[-1..10,-1..10] of integer; i,j:integer;m,n:1..6; begin
read(m);read(n);
fillchar(a,sizeof(a),0); a[6,n]:=1;
for i:= 5 downto 1 do for j:=1 to 6 do
a[i,j]:=a[i+2,j-1]+a[i+2,j+1]+a[i+1,j-2]+a[i+1,j+2];彈贸摄尔霁毙攬砖卤庑诒尔肤。 writeln(a[1,m]:3); end.
例4、求最长不下降数字序列。设有一个正整数序列b1,b2,b3,…..bn,对于下标i1 b[I,1]:表示第I项数值本身； b[I,2]: 表是从第I项到最后一项最长不下降序列的长度； 2 / 5 b[I,3]：链接字，表示最长不下降序列经过此项之后，后面继续的项。当b[I,3]=0时表示链接结束。厦礴恳蹒骈時盡继價骚卺癩龔。 源程序： program d4; const n=10; var i,j,k,l:integer; b:array[1..n,1..3] of integer; begin for i:=1 to n do begin readln( b[i,1]); b[i,2]:=1; b[i,3]:=0 end; for i:=n-1 downto 1 do begin l:=0;k:=0; for j:=i+1 to n do if (b[j,1]>b[i,1]) and (b[j,2]>l) then begin l:=b[j,2];k:=j end; if l>0 then begin b[i,2]:=l+1;b[i,3]:=k end; end; l:=1; for j:=2 to n do if b[j,2]>b[l,2] then l:=j; writeln('max:=',b[l,2]); while l<>0 do begin write(b[l,1]:4); l:=b[l,3]; end; writeln; end. 例5、挖地雷：在一条河提上有若干个地雷坑，每个地雷坑中埋有一定数量的地雷，地雷坑编号为1，2，3。。。n。如下图所示;茕桢广鳓鯡选块网羈泪镀齐鈞。 地雷1 坑号 地雷8 数量 2 14 3 2 4 17 5 33 6 26 7 15 8 17 9 19 10 6 同时在每个地雷坑中都有一张说明书（最后一个地雷坑除外），说明书指出，在挖完该地雷 3 / 5