思路1：最自然的思路应该是穷举思路要放弃，新建一个数组用于储存n从0到n-1的所有可能情况，对于n，第一步只有两种走法，走一步或者走两步，而a[n-1]和a[n-2]都是提前求好的，所以直接带入求和即可
int climbStairs(int n){
if(n < 3)
return n;
int *a = (int *)malloc((n + 1)* sizeof(int));
a[0] = 0;
a[1] = 1;
a[2] = 2;
for(int i = 3; i <= n; i++){
a[i] = a[i-1] + a[i-2];
}
return a[n];
}
思路2:对于思路1中的数组，实际上我们只需要知道n之前的两个数字就可以了，不需要记录从0-n的所有数字，所以维护两个变量就可以了。
int climbStairs(int n){
if(n < 3)
return n;
int first = 1;
int second = 2;
int result = 0;
for(int i = 3; i <= n; i++){
result = first + second;
first = second;
second = result;
}
return result;
}
思路3:对于要记录的两个数，实际上可以直接递归,可惜提交的时候会报超时 saaaaaad
int climbStairs(int n){
if(n < 3)
return n;
return climbStairs(n-1) + climbStairs(n-2);
}
本系列文章，旨在打造LeetCode题目解题方法，帮助和引导同学们开阔学习算法思路，由于个人能力和精力的局限性，也会参考其他网站的代码和思路，如有侵权，请联系本人删除。
