N = gets.to_i dp = Array.new(N+1){ 0 } dp[0] = 0 dp[1] = 1 dp[2] = 2 3.upto(N) do | i | dp[i] = dp[i-1] + dp[i-2] end p dp[N]