【LeetCode】Climbing Stairs

题目描述：

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?

题目分析：

思路一：递归

有两种情况上最后一节台阶，一种是直接一节上，一种是两节一块上，即

climbStairs（n）=climbStairs(n-1)+climbStairs(n-2)

用递归即可

但是有一个问题，递归严重超时 

climbStairs（5） = climbStairs（4） +climbStairs（3）

climbStairs（4） = climbStairs（3） +climbStairs（2） //其实climbStairs（3）在上一步已经计算过一次了，重复计算递归值导致超时

climbStairs（3） = climbStairs（2） +climbStairs（1）

一种解决的方法是用动态规划，动态申请数组来存贮已经计算出的值，如果存在直接使用，不用再递归计算

思路二：正向用循环的方式来做