Leetcodes: Climbing Stairs (DP)

Climbing Stairs

My Submissions

Total Accepted: 82735 Total Submissions: 233609 Difficulty: Easy

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?

Subscribe to see which companies asked this question

Hide Tags

 Dynamic Programming

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

DP:

From down to top, start from the 3rd stares, we can see the rules:

dp(i)=dp(i-1)+dp(i-2);

where dp(i)  is the number of kinds ways for the ith stair! 

////////////////////////////////////////////////////

//codes

class Solution {

public:

    int climbStairs(int n) {

        //check input

        if(n<4)return n;

        vector<int> dp;

        dp.assign(n+1,0);        

        dp[1]=1;dp[2]=2;dp[3]=3;

        for(int i=4;i<n+1;i++){

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

        }

        return dp[n];

    }

};