« back

Climbing Stairs

Tags : dynamic-programming, leetcode, cpp, easy

Problem Statement - link #

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

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

Examples #

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints #

Solution #


class Solution {
public:
    int climbStairs(int n) {
        int dp[n+1];
        dp[0] = 1;
        for(int i=1; i<n+1; i++){
            int waystoi = 0;
            if(i-2 >= 0)
                waystoi = dp[i-2];
            waystoi += dp[i-1];
            dp[i] = waystoi;
        }
        return dp[n];
    }
};