请问可以通过递归解决的问题， 是否都可以同样地通过动态规划解决呢？
来源：9-4 状态的定义和状态转移 House Robber
ATWJSW
2017-11-03
由于动态规划不使用额外的栈资源，计算过程貌似对堆资源占用也较少(如果需要创建对象的话）， 是否意味着同样一个问题如果能用DP解决应该尽量使用DP？
貌似从可读性的角度出发递归更好，如果需要用到复杂算法时，实际生产工作中是否更多考虑可读性？
写回答
1回答
-
不是！动态规划是一类特殊的递归问题，必须满足最优子结构和重叠子问题的性质才可以使用动态规划。所以你的问题标题的陈述不成立。
当然，如果一个问题满足这样的性质，使用动态规划解决是最好的。最关键的问题不是存储资源的问题，而是时间资源的问题。
如果是动态规划方法和记忆花搜索作比较的话，确实动态规划方法更优，主要是你说的系统资源问题。不过其实对于现代计算机来说，对于大多数情况，递归消耗的存储资源和时间开销近乎可以忽略。此时选择记忆化搜索还是动态规划可以酌情考虑。对于经典的动态规划问题，我个人偏向于直接使用动态规划的写法。但是对于更复杂的问题，我偏向使用记忆化搜索。
012017-11-03
相似问题