社团活动每日一题：第十四天 爬楼梯

前言：这是我们大学社团给我们大一新生布置的每日一题任务，因为本人编程理解有限，参考价值较低。

题目链接https://leetcode-cn.com/problems/climbing-stairs/        动态规划入门，n的范围题目未给出，实际上是1~45，可以用多种方法写出。

方案1：递归法

        这个方法社是从最后一个情况开始计算，然后往前更新，熟练掌握函数的递归用法后应该很容易就能写出：

class Solution {
public:int ans[46];        //n的范围是1~45int find(int x){if(ans[x])return ans[x];return ans[x]=find(x-1) + find(x-2);}int climbStairs(int n) {//solution1 : 递归ans[0] = ans[1] = 1;return find(n);}
};

方案2：dp背包

        和上述方法原理差不多，不过不用函数，是从前往后找的。

class Solution {
public:int ans[46];        //n的范围是1~45int climbStairs(int n) {//solution2 : dp背包if(n==1)return 1;   //这个方法不支持n==1的情况需要特判ans[0] = ans[1] = 1;for(int i=2;i<n;i++)ans[i]=ans[i-1]+ans[i-2];return ans[n-1]+ans[n-2];}
};

         至于为什么要提出两种看起来差不多的解法，是因为这两种方法在这里原理相同，但事实上在算法里，这俩并没有那么大关系。

方案3：滚动数组

        这个方法和dp背包差不多，不过可以把O(n)的空间复杂度给贪了。

class Solution {
public:int climbStairs(int n) {//solution3 : 滚动数组int a=1,b=1,c=1;for(int i=1;i<n;i++){c = a+b;a = b;b = c;       }return c; }
};

        其实这也是许多人一开始就能想到的做法就是了（）