假设你正在爬楼梯。需要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 阶
方案1
递归调用，暴力破解出每一种情况，然后把所有情况累计求和。
public int climbStairs(int n) {if( n == 1 || n == 0 )return 1;return climbStairs(n - 1) + climbStairs(n - 2);}
分析
代码比较简洁易懂，但是代码本身是用递归实现的，所以需要消耗大量的内存空间，所以最后的运行结果超时了。
方案2
通过分析示例，我们可以发现它其实就是一个斐波那契数列，让我们求第n个斐波那契数
public int climbStairs(int n) {if(n==1) return 1;int a = 1;int b = 2;int c;for(int i=3;i<=n ;++i){c = a + b;a = b;b = c;}return b;}
分析
这样写只需要一个简单的循环就可以解决问题，代码写起来也比较简单，而且结果不会超时的，但是这道题是属于动态规划的。
方案3
动态规划解决这个问题。设dp[i]就是i时候的最多方案则
dp[1] = 1;
dp[2] = 2;
dp[3] = dp[2] + dp[1]
......
dp[n] = dp[n-1] + dp[n2]
public int climbStairs(int n) {//这里大小根据自己需要，或者使用 List 也可以int[] dp = new int[100000];dp[1] = 1;dp[2] = 2;for( int i = 3;i <= n;++i ){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
分析
这样写就很好的解决这个问题，在动态规划的世界里，只要找到递推公式，那么答案也就随之出来了。
leetcode | 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
