LetCode 70 계단 오르기.

제목: 계단을 오르고 있다고 가정해 보세요.n 단계가 있어야 옥상에 도착할 수 있습니다.매번 너는 한 계단이나 두 계단을 올라갈 수 있다.너는 옥상까지 올라갈 수 있는 몇 가지 다른 방법이 있니?주의: n을 정하는 것은 정수입니다.예시 1: 입력: 2 출력: 2 해석: 두 가지 방법으로 옥상에 올라갈 수 있다.

1 단계 + 1 단계

2단계 예시 2: 입력: 3 출력: 3 해석: 세 가지 방법으로 옥상에 올라갈 수 있다.

1 단계 + 1 단계 + 1 단계

1 단계 + 2 단계

2단계 + 1단계

이 문제를 보고 머릿속에 떠오르는 것은 바로 동적 기획이다. 무엇이 동적 기획인지, 한마디로 네가 이미 계산한 것을 기억하고 이미 계산한 기초 위에서 중첩하여 중복된 계산을 피하는 것이다.
우선, 계단 수를 모두 1로 구성된 수조로 상상해 보자. 예를 들어 8급 계단은 [1,1,1,1,1,1,1,1]이다. 그러면 서로 다른 계단 오르기 방안은 [2,1,1,1,1,1,1],[1,2,1,1,1,1,1],[2,1,1,1],[2,2,2,1,1]과 유사하다.한 계단만 두 걸음 걸을 때 7가지 상황이 나타날 수 있다. 즉, [2,1,1,1,1,1,1],[1,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],[1,1,1,1,2,1,1,1],1두 계단을 두 걸음 걸을 때 다음과 같은 상황이 나타날 수 있다. [2,2,2,1,1,1,1,1],[2,1,2,1,1,1],[2,2,2,1,2,2,1,1,1,1,1,1,1,1],[2,1,1,1,1,1,1,1,1,1,1,1,1,1,2,1,1,1,1,1,1,2,2,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,2,1,1,1,2,1,1,1,2,1,1,1,1,2,1,1,1,1,1,1,1,1,1,, 1,1], [1, 2, 1, 2, 1], [1, 2, 1, 1, 1, 1, 2]...여기서 두 번 두 걸음을 걷는 상황은 모두 한 번에 두 걸음을 걷는 기초에서 나온 것이다. 구체적으로는 한 번에 두 걸음을 걷는 그 두 걸음 다음에 두 걸음을 걷는 위치를 선택한다. 이렇게 하면 중복되는 두 걸음 상황을 피하고 결과를 완전하게 반복할 수 있다. 이 방안을 바탕으로 나는 첫 번째 알고리즘을 썼다.

  func climbStairs(_ n: Int) -> Int {
        if n > 0 {
            var count = 1
            for i in 1..

각 계단의 총수는 모두 1이고 하나의 상황이다. 그리고 이 모두 하나의 수조에서 하나의 2를 모으면 여러 가지 상황을 얻을 수 있다. 각 상황에서 모은 그 2를 제거하고 2 다음에 남은 1을 새로운 값으로 만들어 n=0까지 아래로 귀속시킨다. 이때 우리는 1가지 상황만 있다는 것을 안다.
그러나 불행하게도 이런 방식은 시간이 초과되었다. 왜냐하면 안에 너무 많은 중복 계산이 포함되어 있기 때문이다. 숫자 8을 예로 들면 우리가 8을 보내면 그는 귀속 계산치를 6, 5, 4, 3, 2, 1, 0의 결과로 6을 계산하고 4, 3, 2, 1, 0의 결과를 귀속 계산한다. 5는 3, 2, 1, 0의 결과를 계산한다.이를 통해 알 수 있듯이 0의 결과, 1의 결과, 2의 결과는 여러 번 반복적으로 계산되고 이런 계산은 필요하지 않다. 그래서 나는 이런 방안을 다시 관찰했다. n=0일 때 1을 직접 낼 수 있고 n=1일 때 1을 직접 낼 수 있으며 n=2일 때 1+(n=0)로 볼 수 있다.이렇게 유추하면 n = 0: 1 n = 1: 1 n = 2: 1 + (n = 0) n = 3: 1 + (n = 1) + (n = 0) n = 4: 1 + (n = 2) + (n = 1) + (n = 0) n = 5: 1 + (n = 3) + (n = 2) + (n = 1) + (n = 0)...n=4: (n=3) + (n=2) n = 5: (n=4) + (n=3) 따라서 누적법을 통해 n=2부터 n=0과 n=1 n=2를 적으면 (n=0) + (n=1) n=1과 n=2 n=3을 적으면 (n=2) + (n=1) (n=1) +(n=1) (n=1) 를 적으면 n=2와 n=3 n=4는 (n=3) + (n=2)...최종적으로 답을 얻다

    func climbStairs(_ n: Int) -> Int {
        
        if n > 1 {
            var lastTwo = 1
            var addCount = 1
            for index in 2...n {
                let tLast = lastTwo
                lastTwo = addCount
                addCount += tLast
            }
            return addCount
        } else {
            return 1
        }   
    }

제출 통과