Generalized staircase

Challenge

Implement:

long long count_staircase_ways(int n, int max_step);

Count the ways to climb n stairs taking between 1 and max_step steps at a time, using memoized recursion. count(0)=1.

Input format

n >= 0, max_step >= 1.

Output format

Number of ways.

Constraints

Memoize to avoid exponential blowup.

Starter code

#include <stddef.h>
/* Number of ways to climb n stairs taking between 1 and max_step steps at a time (memoized recursion). count(0)=1. */
long long count_staircase_ways(int n,int max_step){ (void)n;(void)max_step; return 0; }

Common mistakes

Plain recursion without memoization is exponential and times out.

Edge cases to handle

0 stairs has 1 way (do nothing).

Background lessons

• Memoized recursion