두 개의 숫자 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이면 true를 반환하고, 그렇지 않으면 false를 반환
- dp(i + 1, 0) mod m + dp(i + 1, K + 1) mod m을 반환합니다.
- 메인 방법에서 다음을 수행하십시오. -
- dp(0, 0) 모드 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