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

파이썬에서 n 자리의 스테핑 수를 계산하는 프로그램

<시간/>

숫자 n이 있다고 가정하면 n자리의 스테핑 숫자의 수를 찾아야 합니다. 우리가 알고 있듯이 모든 인접한 숫자의 절대 차이가 1일 때 숫자를 스테핑 숫자라고 합니다. 따라서 숫자가 123이면 이것은 스테핑 숫자이지만 124는 그렇지 않습니다. 답이 매우 크면 결과 모드 10^9 + 7을 반환합니다.

따라서 입력이 n =2와 같으면 스테핑 번호가 [12, 23, 34, 45, 56, 67, 78, 89, 98, 87, 76, 65, 54, 43, 32, 21, 10]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • m :=10^9 + 7
  • n이 0과 같으면
    • 0을 반환
  • n이 1과 같으면
    • 10 반환
  • dp :=값 1로 채워진 크기 10의 목록
  • n - 1회 반복, 수행
    • ndp :=값 0으로 채워진 크기 10의 목록
    • ndp[0] :=dp[1]
    • 1에서 8 사이의 i에 대해 다음을 수행합니다.
      • ndp[i] :=dp[i - 1] + dp[i + 1]
    • ndp[9] :=dp[8]
    • dp :=ndp
  • return(dp[인덱스 1부터 끝까지]의 모든 수의 합) mod m

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, n):
      m = (10 ** 9 + 7)
      if n == 0:
         return 0
      if n == 1:
         return 10
      dp = [1] * 10
      for _ in range(n - 1):
         ndp = [0] * 10
         ndp[0] = dp[1]
         for i in range(1, 9):
            ndp[i] = dp[i - 1] + dp[i + 1]
         ndp[9] = dp[8]
         dp = ndp
      return sum(dp[1:]) % m

ob = Solution()
n = 3
print(ob.solve(n))

입력

3

출력

32