动规路径.pptVIP

最短通路问题 滑雪 方格取数 * * 如下图所示为一个数字三角形，请编程计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。（只要求输出总和） 规定： ⑴一步可沿左斜线向下或右斜线向下走； 　 ⑵图形行数小于等于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. 阶段 状态 决策 状态转移方程 4 5 2 6 5 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