We consider only those Fibonacci numbers which are less than n , where we can consider fib [ 30 ] to be the upper bound as this will cross 10 ^ 5
fib = [ 0 for i in range ( 30 ) ] NEW_LINE fib [ 0 ] = 0 NEW_LINE fib [ 1 ] = 1 NEW_LINE for i in range ( 2 , 30 ) : NEW_LINE INDENT fib [ i ] = fib [ i - 1 ] + fib [ i - 2 ] NEW_LINE DEDENT