Problem statement

https://binarysearch.com/problems/Consecutive-Wins/

Solution

We will keep in dp number of sequences which end with exaclty 0, 1, ..., k wins.

Complexity

It is O(nk) for time and O(k) for space.

Code

class Solution:
    def solve(self, n, k):
        M = 10**9 + 7
        dp = [1] + [0] * k
        for i in range(n):
            dp = [sum(dp) % M] + dp[:-1]

        return sum(dp) % M