Bob has ladder. He wants to climb this ladder, but being a precocious child, he wonders about exactly how many ways he could to climb this `n` size ladder using jumps of up to distance `k`.

Consider this example...

n = 5\
k = 3

Here, Bob has ladder of length 5, and with each jump, he can ascend up to 3 steps (he can either jump step 1 or 2 or 3). This gives the below possibilities

```
1 1 1 1 1
1 1 1 2
1 1 2 1 
1 2 1 1
2 1 1 1
1 2 2
2 2 1
2 1 2
1 1 3
1 3 1
3 1 1
2 3
3 2
```

Your task to calculate number of ways to climb ladder of length `n` with upto `k` steps for Bob. (13 in above case)

Constraints:

```python
1<=n<=50
1<=k<=15
```

_Tip: try fibonacci._

Difficulty: introductory

Starter code:

def count_ways(n, k):
	

Solutions:
from collections import deque

def count_ways(n, k):
    s,d = 1,deque([0]*k)
    for i in range(n):
        d.append(s)
        s = 2*s-d.popleft()
    return s-d.pop()

from functools import lru_cache

@lru_cache(maxsize=None)
def count_ways(n, k):
    if n < 0:
        return 0
    elif n <= 1:
        return 1
    return sum(count_ways(n-i, k) for i in range(1, k+1))


def count_ways(n, k):
    dp = []
    for i in range(k):
        dp.append(2 ** i)
    for i in range(k, n):
        dp.append(sum(dp[-k:]))
    return dp[~-n]

def count_ways(n, k):
    ways = [None] * (n + 1)
    ways[0] = 1
    for i in range(1, n + 1):
        total = 0
        for j in range(1, k + 1):
            if i - j >= 0 : total += ways[i-j]
        ways[i] = total
    return ways[n]

def count_ways(n, k):
    kfib = [0 for _ in range(k-1)] + [1]
    for i in range(n):
        kfib.append(sum(kfib[i:i+k]))
    return kfib[-1]

from functools import lru_cache

@lru_cache(None)
def count_ways(n, k):
    return sum(count_ways(n - a, k) for a in range(1, min(n, k) + 1)) if n else 1

from functools import lru_cache

@lru_cache(maxsize=None)
def count_ways(n, k):
    return n==0 or sum(count_ways(n-x, k) for x in range(1, min(n, k)+1))

from collections import deque

def count_ways(n, k):
    rs = deque(maxlen=k)
    rs.append(1)
    for _ in range(n):
        rs.append(sum(rs))
    return rs[-1]

def count_ways(n, k):
    list_ = []
    for i in range(k):
        list_.append(2**i)
    
    print(list_)
    
    for i in range(n-k):
        list_.append(sum(list_[-k:]))
    
    print(list_)
    
    return list_[n-1]


def count_ways(n, k):
    steps = [1] * (n + 1)
    for i in range(1, n + 1):
        if i <= k:
            steps[i] = sum(steps[j] for j in range(0, i))
        else:
            steps[i] = sum(steps[i - j] for j in range(1, k + 1))
    return steps[-1]