题目要求（必会，高频题）
有一个爬楼梯的任务。 需要n步才能达到顶。每次可以爬1或2步。 通过多少不同的方式登顶？
注意：给定n将是一个正整数。
示例
Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
- 1 step + 1 step
- 2 steps
>Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
- 1 step + 1 step + 1 step
- 1 step + 2 steps
- 2 steps + 1 step
解题思路
因为每次只能走一步或者两步， 所以在到达n层之前只可能有两种情况：在 n-1层走一步，或者n-2层走两步。接着，我们继续分析，到达n-1层和n-2层同样也是只有两种方法，如此下去，我们可以发现这是一个递归问题。
(1) 所以第一种方法我们可以根据递归来进行解决。
class Solution {
public:int climbStairs(int n) {
if(n==1||n==2) return n;else return (climbStairs(n-1) + climbStairs(n-2)); }
};
缺点 递归方法就是重复计算很多，导致耗时很长，时间成指数级增长，n较大时，可能会超出时间不会AC。
(2) 动态规划思想解决（强推！！！）
爬楼梯数目其实是一个斐波拉契数列。
当一个问题可以分解成若干重复的子问题时，动态规划的思想非常实用：
只需要将子问题求解一次，以后再遇到，直接调用。
关键是找到一个转移方程，由于斐波拉契数列的特点（前两项初值1，1。从第3项开始，每一项都等于前两项之和
Fibonacci sequence），以及解法1中给出的递归式关系，我们能够得到状态转换方程：
dp[i] = dp[i-1] + dp[i-2];
程序中数组 dp[n+1] ，n为字符个数。
dp[i]表示的含义：以索引i结尾的子字符串之和。
class Solution {
public:int climbStairs(int n) {
int dp[n+1];dp[0] = 1;dp[1] = 1;for(int i=2;i<n+1;++i)dp[i] = dp[i-1] + dp[i-2];return dp[n];}
};