Problem:

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Analysis:

Solutions:

C++:

    int climbStairs(int n) {
        if(n == 0)
            return n;

        vector<int> different_ways;
        different_ways.push_back(1);
        for(int i = 1; i < n; ++i) {
            if(i == 1)
                different_ways.push_back(2);
            else
                different_ways.push_back(different_ways[i - 1] + different_ways[i - 2]);
        }
        
        return different_ways[n - 1];
    }

Java :

Python: