what is the complexity of recursive summation

Question

Can someone tell me the exact complexity of this recursion ? this is actually formula for below question ( solved in recursive brute force way )

There is n steps stairs and a person standing at the bottom want to reach at top. Person can take max k steps at a time ( i.e. he can take 1, 2 , 3,.. upto k steps).Count how many ways person can climb the stairs.

f(n,k) = \begin{cases} \sum_{i=1}^k f(n-i,k) \, & \text{if $k$ > 1} \\\\ 1, & \text{if $k$ = 1} \end{cases}

Answer 1

Since this problem is tagged dynamic-programming, here are my two cents on how this can be solved in $O(n)$ memory and $O(n)$ time using dynamic-programming.

The key-idea is maintaining a prefix-sum sequence (as an array in memory). It is a sequence that satisfies the property pre[i] = f[0] + f[1] + ... + f[i]. Consider the base-states: pre[i] := 0 for i < 0 and pre[0] = f[0] = 1. Now we recurse:

for i in range[1, n]:
  f[i] = pre[i - 1] - pre[(i - k) - 1]
  pre[i] = pre[i - 1] + f[i]

If you're not familiar with prefix-sums, note that I employed the fact that f[i] + f[i + 1] + ... + f[j] is the same as pre[j] - pre[i - 1].