Number of ways to climb a flight of stairs

This project was inspired by the YouTube video, Amazon Coding Interview Question – Recursive Staircase Problem.

The recursive solution is quite intuitive. Unfortunately, this solution’s complexity is quite bad, factorial.

Anyways, about a day after I watched this video, a better solution occurred to me as I was walking about. I thought it would be a fun little project to explain the maths behind my quicker solution.

Background Maths

Calculating Combinations (Binomial Coefficients) Efficiently

Main Posts

Number of ways to climb a flight of stairs when taking one, two, three, … steps at a time (Java, recursive)
Number of ways to climb a flight of stairs when taking one, two, three, … steps at a time (faster than recursive) Part 1: Simple Example

GitHub Repository

The recursive and faster than recursive solutions can be found here.

Staircase-Problem