本文共 1507 字，大约阅读时间需要 5 分钟。

一、题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

二、解题思路

（动态规划第二题，第一题在我的第42题——斐波那契数列）

根据题意，我们来分析一下：

假设有1阶台阶，只有一种方法，这个毋庸置疑；

假设有2阶台阶，这时有两种方法，一次爬一阶爬两次 或者 一次爬两阶

假设有3阶台阶，分两种情况：

  第一种：先爬一阶，剩下两阶台阶没有爬，这时考虑的问题就是2阶台阶怎么爬的问题了

  第二种：先爬两阶，剩下一阶台阶没有爬，这时考虑的问题就是1阶台阶怎么爬的问题了

总的爬台阶方法数 = 先爬一阶的情况+先爬二阶的情况

假设有4阶台阶，分两种情况：

  第一种：先爬一阶，剩下三阶台阶没有爬，这时考虑的问题就是3阶台阶怎么爬的问题了

  第二种：先爬两阶，剩下两阶台阶没有爬，这时考虑的问题就是2阶台阶怎么爬的问题了

总的爬台阶方法数 = 先爬一阶的情况+先爬二阶的情况

有没有发现什么规律呢？问题是不是可以归纳如下：

假设有n阶台阶，也分两种情况：

​ 先爬一阶，剩下 n-1 阶台阶没有爬，这时考虑的问题就是 n-1 阶台阶怎么爬的问题了

​ 先爬两阶，剩下 n-2 阶台阶没有爬，这时考虑的问题就是 n-2 阶台阶怎么爬的问题了

n阶台阶爬的方法数记做 f(n)

最后的问题就抽象出：f(n) = f(n-1) + f(n-2)

因为每一次只能爬1级或者2级，所以f(x)只能从f(x-1)和f(x-2)转移过来，而我们就需要对这两项的贡献求和，可以从下面发现规律,加入从0级台阶开始：

f(0) = 1; f(1) = 1; f(2) = 2; f(3) = 3; f(4) = 5; f(5) = 8; … 能够发现这是一个斐波那契数列，其实是可以用实现斐波那契数列是我方式来实现的，下面也给出代码，但有些测试用例过不去，不推荐。

三、代码演示

class Solution {
        public int climbStairs(int n) {
           //因为是从0阶台阶开始算起的，所以数组空间大小声明为n+1        int[] dp = new int[n+1];        //上到第 0 层阶梯的方法数只有一种。        dp[0] = 1;        //上到第 1 层阶梯的方法数有一种        dp[1] = 1;        //从第二阶台阶开始遍历，第二阶台阶是爬第0阶和第1阶台阶的方法数之和        for(int i=2; i<=n; i++){
               //最后到第n个台阶，得到结果正好遍历完            dp[i] = dp[i-1] + dp[i-2];        }       return dp[n];    }}

斐波那契方法实现

//这是用递归实现斐波那契数列的代码，测试用例44过不去，不推荐class Solution {
        public int climbStairs(int n) {
            if(n==0){
                return 1;         }         if(n==1){
                return 1;         }         return climbStairs(n-1)+climbStairs(n-2);     } }

转载地址：http://blgki.baihongyu.com/