class Solution {

public:

    /**

     * @param n: An integer

     * @return: An integer

     */

    int climbStairs(int n) {

        // write your code here

        if(n==0)

        return 1;

        int sum[n];

        sum[0]=1;

        if(n>1)

        sum[1]=2;

        for(int i=2;i<n;i++)

        sum[i]=sum[i-1]+sum[i-2];

        return sum[n-1];

    }

};