leetcode: 509. Fibonacci Number

problem

• https://leetcode.com/problems/fibonacci-number/

dp: top-down

class Solution {
    fun fib(n: Int): Int {
        if (n == 0) return 0
        if (n == 1) return 1
        
        val dp = IntArray(n + 1) { 0 }
        dp[0] = 0
        dp[1] = 1
        for (i in 2..n) {
            dp[i] = dp[i - 1] + dp[i - 2]
        }    
        return dp[n]
    }
}

dp: bottom-up

class Solution {
    val dp = IntArray(31) { 0 } // 0 <= n <= 30
    
    fun fib(n: Int): Int {
        if (n <= 1) return n // base condition
        
        if (dp[n] != 0) return dp[n] // memoization
        
        dp[n] = fib(n - 1) + fib(n - 2)
        return dp[n]
    }
}

O(1) space

class Solution {
    fun fib(n: Int): Int {
        if (n <= 1) return n
        
        var a = 0
        var b = 1
        var i = 2
        while(i <= n) {
            val sum = a + b
            a = b
            b = sum
            i++
        }
        return b
    }
}