Teaching Kids Programming – Compute the Number of Consecutive Ones Less than K using Top Down Dynamic Programming Algorithm (Recursion + Memoziation)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given integers n and k. Given that n represents the number of games you will play, return the number of ways in which you win k or less games consecutively. Mod the result by 10 ** 9 + 7.

Constraints
n ≤ 10,000
k ≤ 10
Example 1
Input
n = 3
k = 2
Output
7
Explanation
Here are the ways in which we can win 2 or fewer times consecutively:

“LLL”
“WLL”
“LWL”
“LLW”
“WWL”
“LWW”
“WLW”

Hints:
Try to think recursively in terms of consecutive wins till the index.

Compute the Number of Consecutive Ones Less than K using Top Down Dynamic Programming Algorithm (Recursion + Memoziation)

The first obvious solution will be to list all possible outcomes and then check to see if it has less or equal than K wins (ones). Each game has two outcomes Win or Lose, and N games lead to O(2^N) time complexity. To check each requires O(N) time thus overall O(N*2^N) time, not practical for big N.

Let’s say we have played i games (from 0 to i-1) and have j consecutive wins, and next game i+1, we have two outcomes: either win and increment the streak to j+1, or lose and then reset the streak to zero. Thus, sum up:

When j is larger than k,
When i reaches the end (n), we have played all games, we need to return 1 if j is less than or equal to k, otherwise zero.

We can implement this reccurence formula (similar to Fibonacci Numbers) using Top Down Dynamic Programming Algorithm, aka Recurison with Memoization:

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def solve(self, n, k):
 
        @cache 
        def f(i, j):
            if j > k:
                return 0
            if i == n:
                return 1
            return f(i + 1, 0) + f(i + 1, j + 1)
 
        # start with first game and zero consecutive wins
        return f(0, 0) 

class Solution:
    def solve(self, n, k):

        @cache 
        def f(i, j):
            if j > k:
                return 0
            if i == n:
                return 1
            return f(i + 1, 0) + f(i + 1, j + 1)

        # start with first game and zero consecutive wins
        return f(0, 0) 

We use the magic keyword @cache (or @lru_cache(None)) to remember the state that we have computed. The total number of states is N*K and thus the time/space complexity is O(N*K)

–EOF (The Ultimate Computing & Technology Blog) —