台阶的走法

难度：T2

【知识点：一维动态规划】

前置知识：数组、循环、状态与转移。

题目描述

从第 $0$ 级地面出发，每次向上走 $1$ 级或 $2$ 级，恰好走到第 $n$ 级。求不同走法数。步骤顺序不同算不同走法。$n=0$ 时什么也不做是一种走法。

输入格式

一行一个整数 $n$。

输出格式

一行一个整数，表示走法数量，不取模。没有走法则输出 0。

样例输入

4

样例输出

5

样例解释

五种步骤序列为 $(1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2)$。

数据范围

$0\le n\le40$。