Computer >> 컴퓨터 >  >> 프로그램 작성 >> Python

파이썬에서 k번 이동하고 처음으로 돌아갈 수 있는 방법의 수를 확인하는 프로그램

<시간/>

우리가 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