Climbing stairs

Challenge

Implement:

long long climb_stairs(int n);

Return the number of distinct ways to climb n stairs taking 1 or 2 steps at a time. climb(0)=1. 0 <= n <= 90.

Input format

n in [0,90].

Output format

Number of ways.

Constraints

Same recurrence as Fibonacci, shifted.

Starter code

#include <stddef.h>
/* Number of ways to climb n stairs taking 1 or 2 steps at a time. climb(0)=1. 0<=n<=90. */
long long climb_stairs(int n){ (void)n; return 0; }

Common mistakes

Off-by-one in the base cases (climb(0) is 1, not 0).

Edge cases to handle

climb(0)=1, climb(1)=1, climb(2)=2.

Background lessons

• Bottom-up DP: Fibonacci & stairs