动规-路径.ppt

如下图所示为一个数字三角形,请编程计算从顶到底的某处的一条路径,使该路径所经过的数字总和最大。(只要求输出总和) 规定: ⑴一步可沿左斜线向下或右斜线向下走; ⑵图形行数小于等于 100 ; ⑶三角形中的数字为 0,1,…, 99 ; 输入:右下图数据应以如下所示格式输入 5(行数)7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出: 30数字三角形按照三角形的行进行阶段划分,若行数为 n,则可把问题看做一个 n-1 个阶段的决策问题。先求出第 n-1 阶段各点到第 n行的最大和,再依次求出第 n-2 阶段、第 n-3 阶段…第1阶段各点至第 n行的最大和。设 f[i,j] 为从第 i阶段中的第 j个点至第 n行的最大和; 由于 f[i,j] 只和第 i+1 阶段的状态和本阶段的点有关系,符合无后效性原则;在每一个阶段都要求出这个阶段的各个点到第 n行的最大和,也符合最优化原则。因此可以用动态规划的方法来求解,以走到每一行时所在的位置作为状态,决策就是向左下走或向右下走。其状态转移方程可以写为: f[i,j]=max{ a[i,j]+f[i+1,j] , a[i,j]+f[i+1,j+1] } ( i=1,2,3,4, …,n-1, 1<=j<=i ) f[n,j]=a[n,j] ( 1<=j<=n ){初始状态} 最后, f[1,1] 即为所求。 var n,i,j:integer; a:array[1..100,1..100] of integer; f:array[1..100,1..100] of integer; begin readln(n); for i:=1 to n do for j:=1 to i do read(a[i,j]); for i:=1 to n do f[n,i]:=a[n,i]; for i:=n-1 downto 1 do for j:=1 to i do if f[i+1,j]>f[i+1,j+1] then f[i,j]:=f[i+1,j]+a[i,j] else f[i,j]:=f[i+1,j+1]+a[i,j]; writeln(f[1,1]); end. 阶段状态决策状态转移方程 45265 7 12 10 10 20 13 10 23 21 30 下图所示是城市道路示意图。每条边上的数字为该段街道的长度。求从 A到B地(只允许往右和往上走)的最短路径长度。 1 3 2 3 2 2 1 4 2 3 4 5 2 3 1 2 2 3 2 1 4 2 2 1 1 2 2 3 3 3 4 A(0,0) B(3,4) 街道最短路径我们以图中的对角线行来划分阶段,共 m+n 个阶段。设 d[i,j] 表示点(0,0) 到点(i,j) 的最短路径长度, v[i,j] 表示点(i-1,j) 到点(i,j) 的竖向距离, h[i,j] 表示点(i,j-1) 到点(i,j) 的横向距离,则 d[i,j]=min{ d[i-1,j] +v[i,j] , d[i,j-1] +h[i,j] } 1 3 2 3 2 2 1 4 2 3 4 5 2 3 1