假设你正在爬楼梯。需要 n阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
image
思路：
前期分析：
动态规划：将一个大问题划分为若干个子问题，先求解子问题，然后就合并解决大问题。 子问题之间是有关系的，即不是独立的子问题，这个就是和分治法的区别，分治法是独立的。
动态规划中，必须保证重复子问题只运行一次，所以就需要空间来记录。一般用 迭代。而分治法 一般用 递归。
具体问题分析：
将这个爬完这个n层的楼梯，分解。设想，怎么样才能在最后的时候一次到达第n层，这时就是，在n-1层（接下来走1步），或者n-2层（接下来走2步）。即最后想要到达的最后一层的时候，最后一步，必需是在n-1，或者n-2层，两种情况。
如何到达n-1层？就用上面的思路，最后一步在 （n-1）- 1层或者 （n-1）-2层
··········
直到1，0层；
我们会发现 这个就是 斐波拉！
int climbStairs(int n) {
int a = 1,b = 1,c = 1;
if(n == 0 || n== 1){
return c;
}
for( int i = 0;i<n-1;i++){
c = a+b;
a = b;
b = c;
}
return c;
}
