Climbing Stairs

마지막 이동을 기준으로 n 계단까지 올라가는 방법을 나눠 보세요. 1계단으로 끝나는 등반 방법은 그 전에 n-1 계단에 서 있었고, 그런 방법은 ways(n-1)개입니다. 2계단으로 끝나는 등반 방법은 n-2 계단에 서 있었고, 그런 방법은 ways(n-2)개입니다. 모든 등반 방법은 둘 중 한 가지로 끝나며 두 가지 모두로 끝나는 경우는 없으므로, ways(n) = ways(n-1) + ways(n-2)입니다.

재귀에는 두 가지 기본 사례가 필요합니다. 한 계단을 오르는 방법은 하나이고, 두 계단을 오르는 방법은 두 가지입니다(1, 1과 2). 두 경우 모두 답은 n과 같으므로, 함수는 n ≤ 2일 때 n을 반환하고, 그 외에는 합을 반환합니다.

답은 맞지만, 연산량이 폭발적으로 늘어납니다. climbStairs(5)는 3계단까지 오르는 방법을 두 번, 2계단까지 오르는 방법을 세 번 계산하므로 총 9번 호출하며, 호출 횟수는 답 자체처럼 증가합니다. n = 45일 때 함수는 2269806339번 호출하는데, 이는 약 2.3 × 10^9번으로 시간 제한을 훨씬 초과합니다. 재귀 깊이는 n단계뿐이므로 스택은 O(n)의 공간을 사용합니다.

재귀가 느린 이유는 값을 기억하지 못하기 때문뿐입니다. 각 개수는 k에만 의존하므로, 단계 k의 개수를 알게 되면 그 값은 바뀌지 않습니다. 단계마다 슬롯 하나씩 있는 배열인 메모를 만들고, 각 개수를 처음 계산할 때 그곳에 저장하세요. 나중에 같은 단계의 개수를 요청하면 다시 재귀하는 대신 해당 슬롯의 값을 읽습니다.

이제 단계 3부터 단계 n까지의 각 개수는 덧셈 한 번으로 한 번씩만 계산됩니다. n = 5일 때 호출은 단계 2까지 한 번 내려간 다음, 답이 3, 5, 8로 돌아오고, 단계 3에 대한 두 번째 요청은 조회로 처리됩니다. 이는 수십억 번 호출하는 대신 O(n) 시간입니다.

메모에는 n + 1개의 숫자가 들어가고 재귀는 여전히 깊이가 n단계이므로 공간 복잡도는 O(n)입니다. 슬롯의 0은 아직 값이 계산되지 않았다는 뜻이며, 실제 개수는 모두 최소 1이므로 안전합니다.

재귀를 거꾸로 뒤집어 보세요. 맨 위에서 시작해 아래로 내려가며 묻는 대신, 맨 아래에서 시작해 위로 쌓아 올리세요. 단계 k의 개수를 계산할 때 k-1과 k-2의 개수는 이미 알고 있으며, 더 오래된 값은 다시 읽지 않습니다. 따라서 메모 전체를 두 변수로 대체할 수 있습니다.

prev에는 단계 k-2의 개수를, curr에는 단계 k-1의 개수를 저장합니다. 단계 1과 2의 개수인 prev = 1과 curr = 2로 시작하세요. 각 단계에서 두 값을 더해 next에 저장한 다음, 쌍을 앞으로 이동합니다. n = 5일 때 쌍은 (1, 2)에서 (2, 3), (3, 5), (5, 8)로 이동하며, curr = 8이 답입니다.

반복문은 한 번씩 더하기를 수행하며 n-2번 실행되므로 시간 복잡도는 O(n)이고, 정수 세 개를 유지하므로 공간 복잡도는 O(1)입니다. prev를 덮어쓰기 전에 next를 계산하세요. 그렇지 않으면 잘못된 값으로 합을 계산하게 됩니다.