运筹学上有一章节专门讲动态规划的，印象比较深刻的有一道爬楼梯问题，用dp思想来解决。
【题目】大概是这样：有n级楼梯，每次只能爬1级或2级楼梯，问爬完总共有多少种方法？
转化为程序描述如下：
输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。
【解析】
根据题目意思，我们采用逆推的形式进行推理：
我们用f(n)表示爬完第n格楼梯的方法总数。第n格楼梯可以直接由第n-1格、第n-2格楼梯直接到达，即原题目可转化为爬完第n-1格和爬完第n-2格楼梯的方法数的总和，即f(n)=f(n-1)+f(n-2).
往下逆推：f(n-1)=f(n-2)+f(n-3) , ...... , f(3)=f(2)+f(1)
爬完2格楼梯有两种方法，即f(2)=2；爬完1格楼梯有一种方法，即f(1)=1.
由此我们不难给出代码：
public class SolutionClimbStairs {
public int climbStairs(int n) {
if(n==1) return 1 ;
if(n==2) return 2 ;
//re用于储存动态变化的阶梯数的结果
int re[] = new int[n];
re[0] = 1 ;
re[1] = 2 ;
if(n>=3){
//递归耗时
//return climbStairs(n-1)+climbStairs(n-2);
//动态规划,存储每一步计算的结果
for(int i = 2 ; i<=n-1 ; i++){
re[i] = re[i-1]+re[i-2];
}
return re[n-1];
};
return 0 ;
}
}
【总结】
上面的代码用一组数组储存每一步计算的结果，避免了递归的时候每次都去计算，提高了计算效率。该算法的时间复杂度O(n)，空间复杂度O(n)，时空复杂度上有优化空间，这里为了便于理解，采用1个数组来储存每一步计算的结果（当批量求n级阶梯问题时性能更加明显）。
该题目运用了一点动态规划的思想，加之递归的实现，解决了爬楼梯的经典问题。
此前也写过一篇类似的文章 ： 用Java实现斐波那契数列
实现方法跟这篇差不多，也是递归思想的应用，可结合一起看。
记录至此，文章完结。
