数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：计算最多连胜k场的获胜方式数量
假设我们有两个数字n和k。其中n表示我们将要玩的游戏数量。我们必须找出以多少种方式我们可以连续赢得k场或更少场游戏。如果答案过大，则将结果模 10^9 + 7。
因此，如果输入类似于n = 3 k = 2，则输出将为7，因为我们可以连续赢得2场或更少场游戏的可能方式是["LLL", "WLL", "LWL", "LLW", "WWL", "LWW", "WLW"]
为了解决这个问题，我们将遵循以下步骤：
- m := 1^9 + 7
- 定义一个函数dp()。它将接收i和K作为参数
- 如果i >= n 或 K > k，则
- 返回K <= k时为真，否则为假
- 返回dp(i + 1, 0) mod m + dp(i + 1, K + 1) mod m
- 从主方法中执行以下操作：
- 返回dp(0, 0) mod m
示例
让我们看看以下实现以获得更好的理解：
def solve(n, k): m = 1**9 + 7 def dp(i, K): if i >= n or K > k: return K <= k return dp(i + 1, 0) % m + dp(i + 1, K + 1) % m return dp(0, 0) % m n = 4 k = 2 print(solve(n, k))
输入
4, 2
输出
5
更新于: 2021年10月18日
260 次浏览
广告