深搜与简单的动态规划

《深搜与简单的动态规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9讲深搜与简单的动态规划深度优先搜索算法的框架:proceduredfs(i);//搜索第i个分量Xibeginifi=n+1找到一个解//ifi=n+1thenexit;//防止数组越界//合适的剪枝优化：最优化剪枝与可行性剪枝forXi∈Si且使得（X1,X2，。。。Xi-1,Xi）满足约束条件dobegin记录满足条件的Xi;//添加相应的标志;dfs(i+1)//删除标志;恢复之前的状态,根据具体情况选择:回溯endend1、数字三角形有一个数字三角形，编程求从最顶层到最底层的一条路所经过位置上数字之和的最大值。每一步只能向左下或右下

2、方向走。下图数据的路应为7->3->8->7->5，和为30。输入：第一行：R(1<=R<=100),数字三角形共有R行；以下R行：依次表示数字三角形中每行中的数字。每个数都是非负的，且<=100.输出：一个正整数，路径上数字之和的最大值。输入样例：5738810274445265输出样例：30738810274445265算法1：深度优先搜索算法DFS：二维数组a[i，j]存储数字三角形。Proceduredfs(sum,i,j:integer);//从a[1,1]到走到第i行第j列即a[i,j]时所取得的值为sumbeginifi=nthen

3、beginifsum>maxthenmax:=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);结果：max738810274445265738810274445265为什么当n较大时速度慢？f:array[0..100,0..100]ofinteger;f[i,j]:(i,j)到最后一行经过数的和的最大值f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[i,j];初始：f

4、[n,i]=a[n,i]目标：f[1,1]算法2：functionmax(a,b:longint):longint;beginifa>bthenexit(a)elseexit(b);end;Proceduredfs(i,j:integer);//求(i,j)到最后一行的最大和beginifi=nthenbeginf[i,j]:=a[i,j];exit;end;iff[i,j]>0thenexit;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;Beginini

5、t;fillchar(f,sizeof(f),0);dfs(1,1);writeln(f[1,1]);End.设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=

6、元素}f[i,j]:=max(f[i+1,j],f[i+1,j+1])+a[I,j];{枚举走法}writeln(f[1,1]);end;functionmax(a,b:integer):integer;beginmax:=a;ifb>maxthenmax:=b;end;依次求从起点(1,1)到点（i，j）的最大值。//正向设f[i,j]为从a[1,1]到达a[i,j]时取得的最大值．根据题意可得出递推关系：f[i,j]=max{f[i-1,j-1],f[i-1,j]｝+a[i,j]初始：f[1,1]:=a[1,1];目标：max{f[n,i]}

7、1=ansthenans:=f[n,i];writeln(ans);end;总结：算法1：一般的搜索（效率很低）。算法2：记忆化搜索（效率高）。算法3和算法4：动态规划算法（效率高）。在一个n*m的棋盘内，一些格子里有垃圾要拾捡。现在

8、有一个能捡垃圾的机器人从左上格子里出发，每次只能向右或者向下走。每次他到达一个点，就会自动把这个点内的垃圾拾掉。问：机器人到达右下角时最