为什么要用动态规划法解题

为什么要用动态规划法解题
首先，看下面一个问题:

【例题1】数字三角形问题。

              7

             3 8

            8 1 0

           2 7 7 4

          5 5 2 6 5

示出了一个数字三角形宝塔。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数≤100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。输人数据：由文件输入数据，文件第一行是三角形的行数N。以后的N行分别是从最顶层到最底层的每一层中的数字。
如输入： 5
7           
3 8         
8 1 0    
2 7 7 4    
4 5 2 6 5   
输出：30
【分析】对于这一问题，很容易想到用枚举的方法（深度搜索法）去解决，即列举出所有路径并记录每一条路径所经过的数字总和。然后寻找最大的数字总和，这一想法很直观，很容易编程实现其程序如下：

program sjx;
const maxn=10;
var
a:array[1..maxn,1..maxn] of integer;
max:longint;
n,i,j:integer;
fname:string;

inputf:text;

proceduretry(x,y,dep:integer;sum:longint);
begin
  if (dep=n) then
   begin
   if sum>max then  max:=sum;
    exit
   end;
  try(x+1,y,dep+1,sum+a[x+1,y]);
  try(x+1,y+1,dep+1,sum+a[x+1,y+1]);
end;
begin
readln(fname);

assign(inputf,fname);

reset(inputf);

readln(inputf,n);
for i:=1 to n do
  for j:= 1 to i do
   read(inputf,a[i,j]);
max:=0;
try(1,1,1,a[1,1]);
writeln(max);
end.

但是当行数很大时，当三角形的行数等于100时，其枚举量之大是可想而知的，用枚举法肯定超时，甚至根本不能得到计算结果，必须用动态规划法来解。
2.2 怎样用动态规划法解题
1.逆推法:

按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的的最大和，再依次求出第n-2阶段、第n-3阶段……第1阶段(起始点)各决策点至第n行的最佳路径。
设：f[i,j]为从第i阶段中的点j至第n行的最大的数字和；
则: f[n,j]=a[n,j]   1<=j<=n

   f[i,j]=max{a[i,j]+f[i+1,j],a[i,j]+f[i+1,j+1]}  1<=j<=i.

   f[1,1]即为所求。

程序如下：

programdatasjx;
const maxn=100;
var
fname:string;
inputf:text;
n,i,j:integer;
a:array[1..maxn,1..maxn] of integer;
f:array[1..maxn,1..maxn] of integer;
begin
readln(fname);
assign(inputf,fname);
reset(inputf);
readln(inputf,n);
for i:=1 to n do
  for j:=1 to i do
   read(inputf,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]:=a[i,j]+f[i+1,j]
    else f[i,j]:=a[i,j]+f[i+1,j+1];
writeln(f[1,1]);
end.   

2. 顺推法

按三角形的行划分阶段，若行数为 n，则可把问题看做一个n-1个阶段的决策问题。先求第2行各元素到起点的最大和

,再依次求出第3,4，5,......,.n-1,n到起点的最大和,最后找第n行的最大值

设f[i,j]为第i行第j列上点到起点的最大和

则 f[1，1]=a[1,1];

      f[i，1]=a[i, 1]+f[i-1,1];

      f[ i，j ]=max{a[i,j]+f[i-1,j-1],a[i,j]+f[i-1,j]}    2<=j<=i

max(f[n,1],f[n,2],.......,f[n,n]}即为所求。

程序如下：

programdatasjx;
const maxn=100;
var
fname:string;
inputf:text;
n,i,j:integer;
a:array[1..maxn,1..maxn] of integer;
f:array[1..maxn,1..maxn] of integer;
maxsum:integer;
begin
readln(fname);
assign(inputf,fname);
reset(inputf);
readln(inputf,n);
for i:=1 to n do
  for j:=1 to i do
   read(inputf,a[i,j]);
fillchar(f,sizeof(f),0);

f[1,1]:=a[1,1];
for i:=2 to n do
  begin
  f[i,1]:=a[i,1]+f[i-1,1];
  for j:=2 to i do
   if f[i-1,j-1]>f[i-1,j] then f[i,j]:=a[i,j]+f[i-1,j-1]
    else f[i,j]:=a[i,j]+f[i-1,j];
  end;
maxsum:=0;
for i:=1 to n do
  if f[n,i]>maxsum then maxsum:=f[n,i];
writeln(maxsum);
end.

说明一下：

1.用动态规划解题主要思想是用空间换时间.

2.本题如果n较大，用2维数组空间可能不够,可以使用1维数组.

程序如下:

programdatasjx;
const maxn=100;
var
fname:string;
inputf:text;
n,i,j:integer;
a:array[1..maxn,1..maxn] of integer;
f:array[1..maxn] of integer;
maxsum:integer;
begin
readln(fname);
assign(inputf,fname);
reset(inputf);
readln(inputf,n);
for i:=1 to n do
  for j:=1 to i do
   read(inputf,a[i,j]);
fillchar(f,sizeof(f),0);
f[1]:=a[1,1];
for i:=2 to n do
  begin
  for j:=i downto 2 do
   if f[j-1]>f[j] then f[j]:=a[i,j]+f[j-1]
    else f[j]:=a[i,j]+f[j];
  f[1]:=a[i,1]+f[1];
  end;
maxsum:=0;
for i:=1 to n do
  if f>maxsum then maxsum:=f;
writeln(maxsum);
end.