动态规划初步.ppt

动态规划初步
山东青岛第二中学
臧方青
一:为理解概念的几个实例
。
一个含有n阶的楼梯,一次可以走1步或2步,从底走到顶一共有几种走法?n<=90。
还记得昨天的基础算法中得这个题的解法吗?
——
f(1)=1
f(2)=2
f(n)=f(n-1)+f(n-2)
算法一:递归
var
n:integer;
function dp(i:integer):longint;
begin
if i=1 then exit(1);
if i=2 then exit(2);
dp:=dp(i-1)+dp(i-2);
end;
begin
readln(n);
writeln(dp(n));
end.
算法二:利用函数实现记忆化搜索
const
maxn=45;
Var
n:integer;
f:array[1..maxn] of longint;
function dp(i:integer):longint;
begin
if i=1 then exit(1);
if i=2 then exit(2);
if f[i]>0 then exit(f[i]);
dp:=dp(i-1)+dp(i-2);
f[i]:=dp;
end;
Begin
readln(n); writeln(dp(n));
end.
算法三:利用过程实现记忆化搜索
const
maxn=90;
var
n:integer;
f:array[1..maxn] of qword;
procedure dp(i:integer);
begin
if i=1 then begin f[i]:=1; exit; end;
if i=2 then begin f[i]:=2; exit; end;
if f[i]>0 then exit;
dp(i-1);
dp(i-2);
f[i]:=f[i-1]+f[i-2];
end;
begin
readln(n);
dp(n);
writeln(f[n]);
end.
算法四:递推
const
maxn=90;
var
n:integer;
f:array[1..maxn] of qword;
procedure dp;
var i:integer;
begin
f[1]:=1; f[2]:=2;
for i:=3 to n do f[i]:=f[i-1]+f[i-2];
end;
begin
readln(n);
dp;
writeln(f[n]);
end.
让我们一起分析每种算法的优劣。
2、数字三角形
有一个数字三角形,编程求从最顶层到最底层的一条路所经过位置上数字之和的最大值。每一步只能向左下或右下方向走。下图数据的路应为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
算法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
时间复杂度怎样?
算法二:记忆化搜索
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);
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])+