Dynamic programming [1] - 피보나치 수열

동적프로그래밍은 간단하게 생각하면, 이전에 도출된 해를 가지고 그 다음 해를 구하는 식으로 푸는것이다.

그러면 이게 문제를 점화식으로 나타낼 수 있는데, 점화식만 도출해 내면 코드는 아주 짧다.

 

가장 유명하고 쉬운 문제는 피보나치 수열이다.

 

피보나치 수열은, 처음 두 값이 주어진다. 수열의 n번째 값을 F(n) 이라고 할 때, F(0) = 0, F(1) = 1 이 주어진다.

그 다음으로 오는 수는 바로 이전 두 값의 합이다.

 

F(0) = 0,

F(1) = 1

F(2) = F(0) + F(1) = 0 + 1 = 1

F(3) = F(2) + F(1) = 1 + 1 = 2

F(4) = F(3) + F(2) = 2 + 1 = 3

...

[0,1, 1, 2, 3, 5, .... ] 

이렇게 나가게 되며, 점화식으로 표현하면 다음과 같다.

F(n) = F(n-1) + F(n-2)

이렇게 점화식이 나왔다면 코드 짜는것은 매우 쉽다!

바로 작은수부터 더해나가면 된다

fun fib(n: Int): Int {
        var F = IntArray(n+1)
        // 문제에 n이 1보다 큰수라면 좋겠으나, 0도 가능한 경우 예외처리 
        if (n == 0) {
            return 0
        }
        
        F[0] = 0
        F[1] = 1
        
        for (i in 2..n) {
            F[i] = F[i-1] + F[i-2]
        }
       
        return F[n]
    }