动态规划初步.ppt

动态规划初步315573063动态规划初步
江苏省华罗庚中学杨志军
常州
动态规划初步
一、引入
【例题1】
设有一个三角形的数塔,顶点为根结点,每个结点有一个整数值。从顶点出发,可以向左走或向右走,如图所示:
若要求从根结点开始,
请找出一条路径,使
路径之和最大,只要
输出路径的和。
动态规划初步
13
15
14
11
24
13
12
11
8
7
6
8
7
26
12
动态规划初步
【问题分析】
①贪心法往往得不到最优解:
贪心法问题所在:眼光短浅。
根据贪心法,则13-11-21和45,而实质上13-8-40和61。
动态规划初步
②若用穷举法:从根结点开始,将所有可能的路径求和,找出最大值,但算法时间复杂性使问题解成为不可能。
当 N=1 P=1
N=2 P=2
N=3 P=4
……
N=K P=2K-1。当N=50,P=249=500万亿条路径。
动态规划初步
数据结构
a:array[1..n,1..n] of integer;
13
11
8
12
7
26
6
14
15
8
12
7
13
24
11
动态规划初步
b[1,1]=a[1,1] (i=1)
b[i,1]=b[i-1,1]+a[i,1]
b[i,i]=b[i-1,i-1]+a[i,i] (i>1)
b[i,j]=max{b[i-1,j-1],b[i-1,j]}+a[i,j]
动态规划初步
program ex;
const
n=5;
var
i,j,max:integer;
a,b:array[1..n,1..n] of integer;
begin
for i:=1 to n do
for j:=1 to i do
read(a[i,j]);
动态规划初步
b[1,1]:=a[1,1];
for i:=2 to n do
begin
b[i,1]:=b[i-1,1]+a[i,1];
b[i,i]:=b[i-1,i-1]+a[i,i];
for j:=2 to i-1 do
if b[i-1,j-1]>b[i-1,j]
then b[i,j]:=b[i-1,j-1]+a[i,j]
else b[i,j]:=b[i-1,j]+a[i,j];
end;
动态规划初步
max:=b[n,1];
for j:=2 to n do
if max<b[n,j]
then max:=b[n,j];

writeln('max=',max);
end.