# Consecutive Wins

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

## 题目描述

```
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"


```

## 前置知识

* 递归树
* 动态规划

## 公司

* 暂无

## 思路

定义 f(i, j) 表示 i 次比赛连续赢 j 次的总的可能数目。 其实也就是**长度为 n - i 的字符串中连续 w 的次数不超过 j 的总的可能数**，其中 字符串中的字符只能是 L 或 W。

经过这样的定义之后，我们的答案应该是 f(0, 0)。

实际上，也就是问动态规划的转移方程是什么。

对于 f(0, 0)，我们可以：

* 在末尾增加一个 L，也就是输一局。用公式表示就是 f(1, 0)
* 在末尾增加一个 W，也就是赢一局。用公式表示就是 f(1, 1)

用图来表示就是如下的样子：

![图采用力扣加加刷题插件制作](https://p.ipic.vip/kwdjfk.jpg)

不是一般性，我们可以得出如下的转移方程：

$$
f(i, j)=\left{ \begin{aligned} f(i+1, 0) + f(i+1, j+1) & & j < k \ f(i+1, 0) & & j = k \ \end{aligned} \right.
$$

那么我们的目标其实就是计算图中叶子节点（绿色节点）的总个数。

> 注意 f(3,3) 是不合法的，我们不应该将其计算进去。

上面使我们的递归树代码，可以看出有很多重复的计算。这提示我们使用记忆化递归来解决。使用记忆化递归，总的时间复杂度 节点总数 \* 单个节点的操作数。树的节点总数是 n \* k，单个节点的操作是常数。故总的时间复杂度为 $O(n \* k)，空间复杂度是使用的递归深度 + 记忆化使用的额外空间。其中递归深度是 $n$，记忆化的空间为 $n \* k$，忽略低次项后空间复杂度为 $O(n \* k)$

## 代码

代码支持：Python3

Python3 Code:

```py
class Solution:
    def solve(self, n, k):
        @lru_cache(None)
        def dp(i, cnt):
            if i == n:
                return 1
            ans = dp(i + 1, 0)  # place L
            if cnt < k:
                ans += dp(i + 1, cnt + 1)  # place W if I can
            return ans

        return dp(0, 0) % (10 ** 9 + 7)
```

**复杂度分析**

* 时间复杂度：$O(n \* k)$
* 空间复杂度：$O(n \* k)$


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/consecutive-wins.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.