main.cpp

#include <iostream>
#include <vector>
#include "solution.h"

int main()
{
    std::vector<int> ns = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    Solution* sol = new Solution();
    
    for(int& n: ns)
    {
        std::cout << "For " << n << " stairs we have " << sol->climbStairs(n)
        << " ways to climb it" << std::endl;
    }
    
    delete(sol);

    return 0;
}

problem.md

Climbing stairs

From: https://leetcode.com/explore/featured/card/top-interview-questions-easy/97/dynamic-programming/569/

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?

Note: Given n will be a positive integer.

Example 1:

• Input: 2
• Output: 2
• Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps

Example 2:

• Input: 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

solution.cpp

#include "solution.h"

int Solution::climbStairs(int& n)
{
    if (n==1) return 1;
    
    int first = 1;
    int second = 2;
    int third;
    
    for (int i = 3; i < (n+1); ++i)
    {
        third = first + second;
        first = second;
        second = third;
    }
    
    return second;
}

// Elegant but extremely inefficient
// Time complexity is O(2^n)
int Solution::climbStairs_recursive(int& n)
{
    if (n<=1) return 1;
    return climbStairs_recursive(n-1) + climbStairs_recursive(n-2);
}

solution.h

#pragma once

class Solution
{
public:
    int climbStairs(int& n);
    
    int climbStairs_recursive(int& n);
};