LeetCode: Climbing Stairs

문제설명

• 당신은 계단을 오르려고 한다. 계단의 끝까지 올라가기 위해 n 걸음이 필요하다.
• 계단은 한번에 1단계 또는 2단계 씩만 올라갈 수 있다.
• 계단에 끝까지 올라가는 모든 방법의 수는 얼마인가?

문제풀이

• 재귀로 풀 수 있으며, 최적화를 위해 메모이제이션을 사용할 수 있다.
• 동적 프로그래밍으로 풀 수 있다.

1. Brute-force로 풀기

func climbStairs(_ n: Int) -> Int {
    return climbStairsHelper(0, n)
}

func climbStairsHelper(_ i: Int, _ n: Int) -> Int {
    if i > n {
        return 0
    }
    if i == n {
        return 1
    }

    return climbStairsHelper(i + 1, n) + climbStairsHelper(i + 2, n)
}

print(climbStairs(3)) // 3
print(climbStairs(5)) // 8

2. Memoization

func climbStairs_memoization(_ n: Int) -> Int {
    var memo = Array.init(repeating: 0, count: n+1)
    return climbStairsMemoHelper(0, n, &memo)
}
func climbStairsMemoHelper(_ i: Int, _ n: Int, _ memo: inout [Int]) -> Int {
    if i > n {
        return 0
    }
    if i == n {
        return 1
    }
    if memo[i] > 0 {
        return memo[i]
    }

    memo[i] = climbStairsMemoHelper(i + 1, n, &memo) + climbStairsMemoHelper(i + 2, n, &memo)

    return memo[i]
}

print(climbStairs_memoization(3)) //3
print(climbStairs_memoization(5)) //8

3. Dyanmic Programming

// 3. Dynamic Programming
func climbStairs_dynamicprogramming(_ n: Int) -> Int {
    if n <= 2 {
        return n
    }
    var dp = Array.init(repeating: 0, count: n+1)
    dp[1] = 1
    dp[2] = 2
    for i in 3...n {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

print(climbStairs_dynamicprogramming(3)) //3
print(climbStairs_dynamicprogramming(5)) //8
print(climbStairs_dynamicprogramming(6)) //13