台阶走法

题目描述

一个台阶有n阶，上台阶时可以一次走一阶也可以一次走两阶，请你通过递归方法计算走到台阶顶有几种不同的走法。

输入

输入数据包含一行，包含一个正整数n，为台阶数。 输

输出

输出数据包含一行，包含一个整数，为走到台阶顶的不同方法的总个数。

输入样例

4

输出样例

5

样例解释

上四级台阶，有以下五种走法：

$0\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 4$

$0\rightarrow 1\rightarrow 2\rightarrow 4$

$0\rightarrow 1\rightarrow 3\rightarrow 4$

$0\rightarrow 2\rightarrow 3\rightarrow 4$

$0\rightarrow 2 \rightarrow 4$