70-爬楼梯（Climbing Stairs）

题目描述

中文

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

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

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

英文

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.
           

示例1

输入： 2
	输出： 2
	解释： 有两种方法可以爬到楼顶。
	1.  1 阶 + 1 阶
	2.  2 阶
           

示例2

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶
           

题目分析

• 我们先来简单分析：对于一个楼梯，我们一次只能上一阶或者两阶，所以这一步我们会有两种选择，如果我们选择了一阶，那么下一步同样会面临这个问题。所以我们就会得到这样一个公式：n阶总次数 = n-1阶总次数 + n-2阶总次数，这样一来用递归就可以很轻松的完成要求。

class Solution {
    public int climbStairs(int n) {
        if(n == 1)					//递归出口
            return 1;
        if(n == 2)					//递归出口
            return 2;
        else
            return climbStairs(n-1) + climbStairs(n-2);
    }
}
           

• 可是对于递归我们都很了解，他的效率是十分低下的，那么能不能将他优化一下，使得效率有所提升呢？很明显是有的。
• 对于普通递归，我们知道他效率低下的主要方面是因为大量数据的重复计算，这样我们就可以用一个数组把算过的数据存起来，如果下次仍然需要用到，我们就直接查找，这样效率就提高了很多。

class Solution {
    public int climbStairs(int n) {
        int flag[] = new int[n + 1];            //flag存储计算过的台阶数的解决方案
        return climb_Stairs(n,flag);
    }
    public int climb_Stairs(int n, int [] flag) {
        if(n == 1 || n == 0)
            return 1;
        if(n < 0)
            return 0;
        if(flag[n] > 0)
            return flag[n];
        else
            flag[n] = (climb_Stairs(n-1,flag) + climb_Stairs(n-2,flag));
        return flag[n];
    }
}
           

• 到了这里，运行速度已经可以满足LeetCode上的时间限制了，可是有没有办法更快的求出这个题的解呢？答案是有的，那就是使用动态规划，对于动态规划不了解的可以点击这里，那么用动态规划怎么解决这道题目呢？

  如果对动态规划有所了解，那么你一定清楚动态规划的核心步骤是什么。对，没错，就是找到规划方程。那么这道题的
   规划方程到底是什么呢。
             

阶数	步数
1	1
2	2
3	2+1=3
4	3+2=5
5	5+3=8

• 到了这里是不是已经很明了了呢？他是不是让你想到了什么东西？没错，就是斐波那契数列，现在，我们来看这道题的题解。

class Solution {
    public int climbStairs(int n) {
        if(n == 1)
            return 1;
        if(n == 2)
            return 2;
        int a = 1,b = 2,c = 0,i = 2;
        while(i < n){
            c = a + b;
            a = b;
            b = c;
            i++;
        }
        return c;
    }
}
           

最后附上今天的python代码

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        if n == 2:
            return 2
        a = 1
        b = 2
        c = 0
        i = 2
        while i < n:
            c = a + b
            a = b
            b = c
            i += 1
        return c 
           

今天的题目就到此为止了，我们下次再见。