fun fib(n: Int): Int {
    var memo = hashMapOf<Int, Int>();
    var result = 0
    
    for (i in 1..n) {
        if (memo.containsKey(i)) {
            return memo[i]!!
        }        
        
        if (i <= 2) {
            result = 1
        } else {
            result = memo[i - 1]!! + memo[i - 2]!!
        }

        memo[i] = result
    }
    
    return result
}

fun main() {
    for (i in 1..10) {
    	println(fib(i))    
    }
}