LeetCode（初级算法）动态规划篇---爬楼梯

题目

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

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

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

示例 1：

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

示例 2：

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

解析

方法一

可以把他转换成递归公式：a[i]= a[i-1]+a[i-2]

也可以把他抽象地理解成一个二叉树，计算它的叶子节点个数，在满足条件的时候进行计数

代码

public int climbStairs(int n) {
       if(n<0)return 0;  //这是那些不正确的结果
       else if(n==0)return 1;    //这是正确的结果
       return climbStairs(n-1)+climbStairs(n-2);
   }

拓展

public int climbStairs(int n) {
       if(n<0)return 0;  
       else if(n==0)return 1;    
       return climbStairs(n-3)+climbStairs(n-5);   //爬3个台阶或者是5个台阶的组合
   }

优点：

它不仅仅适用于每次爬1与2个台阶的问题，也适用于爬多个台阶的问题

缺点：

速度慢，不仅仅只是因为递归，还有因为它还要排除不正确的组合方式 (1和2的组合不需要)

！！！在LeetCode中这种方法会超出时间限制，但是可以解出答案的

方法二

输入数(N)  1   2   3   4   5   6    7      8

组合数(a)  1   2   3   5   8   13   21     34

可见刚好呈现 a[N]= a[N-1]+a[N-2] （N>2）

代码

public int climbStairs2(int n) {
       int a=1,b=2,c=0;
       if(n==1)return a;
       else if(n==2)return b;

       for(int i =2;i<n;i++) {
           c = a+b;
           a = b;
           b = c;
       }
       return c;  
   }

优点：速度快

缺点：只适用于步数1与2组合的情况