动态规划和记忆搜索的问题
来源：9-9 LCS，最短路，求动态规划的具体解以及更多
慕雪9091725
2018-08-23
bobo老师你好
我觉得LCS问题用记忆化搜索好像要比动态规划合理一些
1是动态规划可能会去求一些无用解，比如当2个字符串的最后一个字符相同时，记忆化搜索就直接跳到了2个字符串的倒数第二个字符上，而动态规划会把所有的与最后一个字符有关的解全部求出来，而且这个过程可能发生多次 如s1="CABCD" s2="DABCD",记忆化搜索就会极快的直接跳到4+s1[0],s2[0]上 而动态规划还是得求出所有可能，2重循环运行6^2次
2出了字符串尾部 记忆化搜索针对头部也可以很方便的完成剪枝 当lcs的返回值就等于当前考虑的这边的元素长度时，另一边就可以不用去考虑了，如s1="ABCFH" s2="AEBECEF"当递归到 s1,4 s2,6 ("ABCF","AEBECE")时这时lcs(3,6)的返回值就是3，代表s1被选完了，于是便可以不去考虑lcs(4,5)了
3回答
-
慕雪9091725
提问者
2018-10-14
嗯嗯，谢谢bobo老师，你也太细心了吧～么么哒～嗯嗯，是的，遇到好多问题都发现把记忆画搜索专成动态规划需要很多技巧，要好好思考便利方式，但是优点却是太明显了，谢谢bobo老师：）
022018-10-14 -
liuyubobobo
2018-10-14
咦？这个问题当初没有回答？
你的分析完全正确。记忆化搜索由于本质是搜索，所以可以进行减枝。
但是，记忆化搜索的问题是：
1）由于使用递归，对于一些问题的一些用例，递归深度过高，可能会导致系统栈溢出
2）由于递归调用的时间消耗，如果状态计算的密度比较大的话，还是动态规划递推效率更高；
3）最最最最重要的，对于动态规划的优化，有很重要的空间上的优化，这种空间上的优化，只能基于递推：）
非常非常赞的思考，我的回答只是补充：）大赞！
继续加油！：）
00 -
慕雪9091725
提问者
2018-08-24
忘了说，针对的是最长公共子序列问题～～
00
相似问题
回答 2
回答 1