What complexity does this 'how many ways to climb' algorithm have?
The solution is the recursive formula:

$S[k] = \sum_{i=1}^mS[k-i]$

For $m=2$ this is the Fibonacci sequence, and the way to program it is with dynamic programming. The complexity of the dynamic programming is $O(m \cdot n)$.

Consider the last step before reaching step $k$, the number of ways to reach $k$ when the last step is $i$, is equal to the number of steps to reach $S[k-i]$