【动态规划】什么是动态规划算法？

[AwesomeDevin]

dynamic programming被认为是一种与递归相反的技术，递归是从顶部开始分解，通过解决掉所有分解出的问题来解决整个问题，而动态规划是从问题底部开始，解决了小问题后合并为整体的解决方案，从而解决掉整个问题。

动态规划在实现上基本遵循如下思路，根据边界条件得到规模较小时的解，小规模问题合并时依据递推关系式进行，也就是说较大规模的问题解可以由较小问题的解合并计算得到。最经典易懂的就是使用递归算法和动态规划算法两种不同的方式来计算斐波那契数列或求阶乘的对比，动态规划算法的特性相当于对计算过程进行了缓存，避免了不必要的重复计算。