动态规划算法总结动态规划基本思路算法实现实例分析参考链接

动态规划

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决

基本思路

动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

算法实现

使用动态规划求解问题，最重要的就是确定动态规划三要素： （1）问题的阶段-----问题的边界 （2）每个阶段的状态-----最优子结构 （3）从前一个阶段转化到后一个阶段之间的递推关系------转态转移公式

实例分析

实例1 爬楼梯

• 问题描述

有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法

• 问题分析
• 代码实现

参考链接