우리가 n 길이 목록의 위치 0에 있고 각 단계에서 오른쪽으로 한 위치 또는 왼쪽으로 한 위치(경계를 초과하지 않음) 이동하거나 동일한 위치에 머무를 수 있다고 가정합니다. 이제 우리가 정확히 k 단계를 걸을 수 있다면 우리가 걸을 수 있는 고유한 걷기 수를 찾아 인덱스 0으로 다시 도달해야 합니다. 답이 매우 크면 mod 10^9 + 7을 반환합니다.
따라서 입력이 n =7 k =4와 같으면 출력은 9가 됩니다. 동작은 다음과 같습니다.
- [오른쪽, 오른쪽, 왼쪽, 왼쪽],
- [오른쪽, 왼쪽, 오른쪽, 왼쪽],
- [머물고 있어, 있어줘, 있어줘],
- [오른쪽, 왼쪽, 유지, 유지],
- [머물다, 머물다, 오른쪽, 왼쪽으로],
- [오른쪽, 유지, 유지, 왼쪽],
- [오른쪽, 유지, 왼쪽, 유지],
- [유지, 오른쪽, 왼쪽, 유지],
- [그대로, 오른쪽으로, 그대로, 왼쪽으로],
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- m :=10^9 + 7
- N :=길이
- dp() 함수를 정의합니다. 이것은 내가, 점프합니다
- 점프가 0과 같으면
- return(i가 0과 같으면 true, 그렇지 않으면 false)
- count :=dp(i, jumps - 1)
- i>=0이면
- count :=count + dp(i + 1, 점프 - 1)
- i <=N - 1이면
- count :=count + dp(i - 1, 점프 - 1)
- 반환 횟수
- 기본 방법에서 다음을 수행합니다.
- dp(0, n) 모드 m을 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, length, n): MOD = 10 ** 9 + 7 N = length def dp(i, jumps): if jumps == 0: return +(i == 0) count = dp(i, jumps - 1) if i >= 0: count += dp(i + 1, jumps - 1) if i <= N - 1: count += dp(i - 1, jumps - 1) return count return dp(0, n) % MOD ob = Solution() n = 7 k = 4 print(ob.solve(n, k))
입력
7, 4
출력
9