숫자 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