有记忆功能的动态规划看不懂啊。。



经典的动态规划自底向上工作,有些较小子问题的解是不需要的。我们目标是只对必要的子问题求解并且只求一次,所以使用自顶向下的方式,
并维护一个类似自底向上动态规划算法法使用的表格。。。。

这里的自顶向上的方式的意思是什么?  是指求f(n)如有必要再求f(n-1),以此类推,从最大的问题出发求解吗??
还有上面最后一张图说只有一个有效单元V(1,2)的值是从表上取到的这是什么意思??


类似自底向上动态规划算法法使用的表格.。。这句话该怎么理解





#百度##google##微软##C++工程师##算法工程师#
全部评论
你要明白自顶向下是一个递归的过程,原始问题会分解成两个子问题,对于子问题继续递归求解。而备忘录法的实质就是"每次计算后,我们会把计算结果保存在表格中",那么当我们遇到一个子问题,我们可以先在表格查找这个子问题是否存在(伪代码的第一句if F[i][j]<0),如果不存在就计算这个子问题,如果存在,F[i][j]里存的就是这个子问题的解,直接跳转到最后一行return F[i][j]。然后考虑这个自顶而下的过程F[4][5]需要求解F[3][3]和F[3][5],这两个子问题继续递归下去,你发现,只有F[1][2]这个子问题,需要求解两遍,第一遍继续求解子问题,第二遍查找!而这次查找也带来了效率的提升,随着表格的表大,查找的比例会更大
点赞 回复
分享
发布于 2015-12-08 11:48
我觉得看起来应该是自顶向下?
点赞 回复
分享
发布于 2015-12-07 22:26
阅文集团
校招火热招聘中
官网直投
点赞 回复
分享
发布于 2015-12-08 16:19
他说的应该是记忆搜索和动态规划。从某种层面上讲都是减少重复计算。从经验上讲一般动态规划可以过的题你用记忆搜索也没问题。
点赞 回复
分享
发布于 2016-09-01 14:25

相关推荐

2 收藏 评论
分享
牛客网
牛客企业服务