动态规划和记忆搜索的问题

Question

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)了

Answer 1

提问者 慕雪9091725 2018-10-14 12:53:48

嗯嗯，谢谢bobo老师，你也太细心了吧～么么哒～嗯嗯，是的，遇到好多问题都发现把记忆画搜索专成动态规划需要很多技巧，要好好思考便利方式，但是优点却是太明显了，谢谢bobo老师：）

• liuyubobobo #1

  大赞！如果觉得记忆化搜索写起来很容易，近乎可以说已经完全掌握递归了：）

• 提问者 慕雪9091725 回复 liuyubobobo #2

  谢谢bobo老师的鼓励～，继续加油：）

Answer 2

liuyubobobo 2018-10-14 12:40:17

咦？这个问题当初没有回答？

你的分析完全正确。记忆化搜索由于本质是搜索，所以可以进行减枝。

但是，记忆化搜索的问题是：

1）由于使用递归，对于一些问题的一些用例，递归深度过高，可能会导致系统栈溢出

2）由于递归调用的时间消耗，如果状态计算的密度比较大的话，还是动态规划递推效率更高；

3）最最最最重要的，对于动态规划的优化，有很重要的空间上的优化，这种空间上的优化，只能基于递推：）

非常非常赞的思考，我的回答只是补充：）大赞！

继续加油！：）

Answer 3

提问者 慕雪9091725 2018-08-24 21:05:34

忘了说，针对的是最长公共子序列问题～～