大漠刀客 - 个人主页动态

2015-12-08 09:48

已编辑

经典的动态规划自底向上工作，有些较小子问题的解是不需要的。我们目标是只对必要的子问题求解并且只求一次，所以使用自顶向下的方式， 并维护一个类似自底向上动态规划算法法使用的表格。。。。 这里的自顶向上的方式的意思是什么？  是指求f(n)如有必要再求f（n-1）,以此类推，从最大的问题出发求解吗？？ 还有上面最后一张图说只有一个有效单元V(1,2)的值是从表上取到的这是什么意思？？ 类似自底向上动态规划算法法使用的表格.。。这句话该怎么理解

H__ack：你要明白自顶向下是一个递归的过程，原始问题会分解成两个子问题，对于子问题继续递归求解。而备忘录法的实质就是"每次计算后，我们会把计算结果保存在表格中"，那么当我们遇到一个子问题，我们可以先在表格查找这个子问题是否存在(伪代码的第一句if F[i][j]<0)，如果不存在就计算这个子问题，如果存在，F[i][j]里存的就是这个子问题的解，直接跳转到最后一行return F[i][j]。然后考虑这个自顶而下的过程F[4][5]需要求解F[3][3]和F[3][5]，这两个子问题继续递归下去，你发现，只有F[1][2]这个子问题，需要求解两遍，第一遍继续求解子问题，第二遍查找！而这次查找也带来了效率的提升，随着表格的表大，查找的比例会更大

0 点赞评论收藏

2015-12-01 21:44

已编辑

苏州大学 C++

六度空间，错在哪了？

原题 #include <stdio.h> #include <stdlib.h> #define MaxSizeQ 10000 #define MaxVertex 10000 int Visited[MaxVertex] ; typedef int VertexType ; typedef int EdgeType ; typedef struct { int rear ; int front ; int queue[MaxSizeQ] ; }Queue ; typedef struct { Verte...

0 点赞评论收藏

关注他的用户也关注了：