动态规划算法

动态规划算法解析与实战

一、算法思想

动态规划算法的基础是最优原理，它是用来解决贪婪算法和分治算法无法解决或者无法简洁高效解决的算法，一般用于求解下列问题：（1）背包问题 （2）最短路径 等。

动态规划和贪婪算法一样，都一个问题的求解都是分为对很多问题的求解的综合，问题最终的解是多次选择的综合结果，但是贪婪算法中，每次选择最优解，之后不可撤回，但是动态规划中需要考察一系列的抉择，然后才能确定一个最优抉择序列是否包含最优抉择子序列，具体就通过下面的例子来说明：