算法训练——动态规划之爬楼梯问题

算法训练——动态规划之爬楼梯问题

运筹学上有一章节专门讲动态规划的，印象比较深刻的有一道爬楼梯问题，用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实现斐波那契数列

    实现方法跟这篇差不多，也是递归思想的应用，可结合一起看。

记录至此，文章完结。