LeetCode - Fibonacci Number, Climbing Stairs

---

문제

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,F(0) = 0,   F(1) = 1 F(N) = F(N - 1) + F(N - 2), for N > 1.

Given N, calculate F(N).

 

Example 1:

Input: 2 Output: 1 Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: 3 Output: 2 Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: 4 Output: 3 Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

 

Note:

0 ≤ N ≤ 30.

---

메모이제이션

recursive 하게 계산하다 보면 중복 되는 계산이 늘어난다.

한번 계산한 값을 다시 사용할 수 있게 일종의 캐시를 만들어 준다.

Space Complexity를 희생해서 Time Complexity를 줄인다.

class Solution {
	//메모이제이션을 위한 extra space
    var cache : [Int : Int] = [:]
    
    func fib(_ N: Int) -> Int {
    	//이미 계산한 값일 땐 뽑아쓴다.
        if cache[N] != nil {
            return cache[N]!
        }
        //계산하지 않은 값일 경우
        if N < 2 {
        //Base case 2 보자 작을 경우 return
            return N
        }else {
        //Base case 아니고 이전에 계산한 값도 아닐 경우 쭉쭉 내려간다.
            var result = fib(N-1) + fib(N-2)
            cache.updateValue(result, forKey: N)
            return result
        }
        
    }
}

만약 구해야 하는 것이 20이라면 

1부터 계산해서 20까지 만들려고 나는 생각을 하려 한다.

그래서인지 재귀함수가 잘 이해되지 않았다.

20을 구해야되면 19를 구해라고 던지고 18을 구해라고 던지고 하다가 값을 아는 1을 구하라 했을 때

return 1로 해서 stack frame 을 파핑! 해가면서 result 를 구해가는 건데

잘 와닫지가 않는다.

Climbing Stairs 문제도 피보나치와 패턴이 같다.

---

문제

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps

Example 2:

Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step

 

Constraints:

• 1 <= n <= 45

---

차이점은 초기값이 다르다.

   //stair fibo
    //0 0  //0 0
    //1 1  //1 1
    //2 2  //2 1
    //3 3  //3 2
    //4 5  //4 3
    //5 8  //5 5

class Solution {
    //0 0  //0 0
    //1 1  //1 1
    //2 2  //2 1
    //3 3  //3 2
    //4 5  //4 3
    //5 8  //5 5
    var cache : [Int:Int] = [0:0, 1:1, 2:2]
    
    func climbStairs(_ n: Int) -> Int {
        if cache[n] != nil {
            return cache[n]!
        }
        if n < 2 {
            return n
        }else {
            var result = climbStairs(n-1) + climbStairs(n-2)
            cache.updateValue(result, forKey: n)
            print(result)
            return result
        }
        
    }
}