Question

动态规划算法是是递归算法么

比如最长公共子序列问题，虽然思考方式是递归的方式，将x序列和y序列递归的减少到空序列求解，但是算法实现上，是从空序列开始一步一步像上计算最长公共序列的的，并非递归算法

动态规划要求问题拥有重叠子问题并记录每次的最优解，我可不可以理解成，所有动态规划问题，都是以递归的思想思考并以自底向上的非递归算法求解的？

Answer 1

总地来说是不同的算法。但一些递归算法可改写成动态规划。
动态规划是空间换时间的算法。当递归运算的中间结果要反复使用时，动态规划可能将指数速度的算法改进为多项式速度（但相应地，空间代价提高）