n개의 계단이 있는 계단이 있고 한 번에 1 또는 2개의 계단을 오를 수 있다고 가정합니다. 계단을 오를 수 있는 고유한 방법의 수를 반환하는 함수를 정의해야 합니다.
단계의 순서는 변경되지 않아야 하므로 단계의 각 다른 순서가 방법으로 간주됩니다. 답이 매우 크면 결과를 10^9 + 7로 수정합니다.
따라서 입력이 n =5와 같으면 8가지 고유한 방법이 있으므로 출력은 8이 됩니다 -
- 1, 1, 1, 1, 1
- 2, 1, 1, 1
- 1, 2, 1, 1
- 1, 1, 2, 1
- 1, 1, 1, 2
- 1, 2, 2
- 2, 1, 2
- 2, 2, 1
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- dp:=n+1 크기의 배열, 0으로 채움
- dp[1]:=1
- 2 ~ n+1 범위의 i에 대해
- dp[i]:=dp[i-1]+dp[i-2]
- dp mod m의 마지막 요소를 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
m =(10**9)+7 class Solution: def solve(self, n): dp=[0 for _ in range(n+2)] dp[1]=1 for i in range(2,n+2): dp[i]=dp[i-1]+dp[i-2] return dp[-1] % m ob = Solution() print(ob.solve(5))
입력
5
출력
8