题解 | #爬楼梯#

思路：到第n阶楼梯只有两种方式，从第n-1阶迈一步和从第n-2阶迈两步。假设f(n)表示从第1阶到第n阶的所有方法数，那么f(n)=f(n-1)+f(n-2).于是利用这个式子可以用递归思想。但是明显递归的复杂度太高，于是考虑迭代的思路，从头开始分析，
当n=1时，f(1)=1;
当n=2时，f(2)=2;
当n=3时，f(3)=f(2)+f(1)=3;
当n=4时，f(4)=f(3)+f(2)=5;
...
于是可以采用迭代的思想，给定一个数组，累加即可。
（1）动态开辟空间的方式

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    int climbStairs(int n) {
        // write code here
        int res;
        int* parr=(int*)malloc(n*sizeof(int));
        if(parr!=NULL)
        {
            *(parr)=1;
            *(parr+1)=2;
           for(int i=2;i<n;i++)
           {
               *(parr+i)=*(parr+(i-1))+*(parr+(i-2));
           }
        }
        res=*(parr+(n-1));
        free(parr);
        parr=NULL;
        return res;
    }
};

（2）使用vector容器

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @return int整型
     */
    int climbStairs(int n) {
        // write code here
        vector<int> dp(n+1,0);
        dp[0]=0;
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};