def ascan; gets.split.map(&:to_i); end @memo = {} def dfs(n,last = nil) return 1 if n == 0 return 0 if n < 0 return dfs(n-1, 1) if last == 2 return @memo[n] if @memo[n] return @memo[n] = dfs(n-2, 2) + dfs(n-1, 1) end p dfs(gets.to_i)