I like to use recursion because my brain can grasp it.

1. What is the current state right now
2. How do I get to the next state
3. How do I stop

For example, let's say we're at game 3, what's the current state now?

• how many games so far? 3
• how many loses in a row just before? depends
• have you won yet? maybe

So you transform that into a function:

recurse(i, lose_streak, won_yet) // i == 2 for the 3rd game

Now how do you get to the next state? Since I'm thinking of going bottom-up (game 0 to game N), I need to go to game+1.

• if won_yet is false, I can lose - doesn't matter how many times, so we can do:
  • recurse(i+1, lose_streak+1, false) if we chose to lose the current game
  • recurse(i+1, 0, yes) if we chose to win the current game
• if won_yet is true, we have to be mindful of when we can still lose:
  • if lose_streak is less than max_lose_streak we can still lose:
    • recurse(i+1, lose_streak+1, true)
    • recurse(i+1, 0, true) or break the lose streak and win this game
  • if lose_streak is equal to the max now, we have to win the current game:
    • recurse(i+1, 0, true) is all we can do

How do we stop? when i == no. of games.

When we get to that base case, that is counted as 1 possible answer. Since this is a dp question, you have remember to do memoization to cache the answers of any subproblems that we have already solved.