文档介绍：动态规划基础
第1页，共89页，2022年，5月20日，15点18分，星期一
内容:
引例
动态规划的概念与原理
例题分析
第2页，共89页，2022年，5月20日，15点18分，星期一
一个含有n阶的楼梯，一次可以走ln(n);
a:=1; b:=2;
for i:=1 to n-2 do
begin
c:=a+b;
a:=b;
b:=c;
end;
writeln(c);
end.
第11页，共89页，2022年，5月20日，15点18分，星期一
算法2—算法5： 重复的部分只计算一次
第12页，共89页，2022年，5月20日，15点18分，星期一
【引例2、数字三角形(IOI’94)】
有一个数字三角形，编程求从最顶层到最底层的一条路所经过位置上数字之和的最大值。每一步只能向左下或右下方向走。下图数据的路应为7->3->8->7->5，和为30。
输入：
第一行：R(1<=R<=100),数字三角形共有R行；
以下R行：依次表示数字三角形中每行中的数字。
每个数都是非负的，且<=100.
输出：一个正整数，路径上数字之和的最大值。
输入样例：
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例：
30
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
第13页，共89页，2022年，5月20日，15点18分，星期一
算法1：深度优先搜索算法DFS：
二维数组a[i，j]存储数字三角形。
Procedure dfs(sum,i,j:integer);
{从a[1,1]到走到第i行第j列即a[I,j]时所取得的值为sum}
begin
if i=n then
begin if sum>max then max:=sum; exit; end;
dfs(sum+a[i+1,j],i+1,j); {向左下方走}
dfs(sum+a[i+1,j+1],i+1,j+1); {向右下方走}
end;
开始时：dfs(a[1,1],1,1);
结果：max
为什么当n较大时速度慢？
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
第14页，共89页，2022年，5月20日，15点18分，星期一
算法2：
//f:array[0..100,0..100] of integer;
//f[I,j] : (I,j) 到最后一行的最大值
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
Procedure dfs(i,j:integer);//求(i,j)到最后一行的最大和
begin
if i=n then
begin f[i,j]:=a[i,j]; exit; end;
if f[i,j]>0 then exit;
dfs(i+1,j);
dfs(i+1,j+1);
f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];
end;
Begin
init;
dfs(1,1);
writeln(f[1,1]);
End.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
第15页，共89页，2022年，5月20日，15点18分，星期一
方法1：从最后一行向起点走//逆向
设F[I,j]:a[i,j]到达第n行a[n,k]（k：1--n）的最大值．
递推关系：
f[i,j]=max{f[i+1,j],f[i+1,j+1]｝+a[I,j]
初始：f[n,i]:=a[n,i]; 1=<i<=n
目标：f[1,1]
算法3：
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
第16页，共89页，2022年，5月20日，15点18分，星期一
procedure work
begin
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 {枚举每行的元素}
f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[I