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"

• 递归树
• 动态规划

• 暂无

# 思路

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

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.