蜜蜂路线

题目描述

一只蜜蜂在下图所示的数字蜂房上爬动，已知它只能从标号小的蜂房爬到标号大的相邻蜂房。问从如图位置爬到n号蜂房，有多少种爬行路线？ 

输入格式

一行，一个整数n。

输出格式

一个整数，表示爬行路线总数。

3

3

4

5

提示

#### 数据范围与提示 $1≤n≤30$ 样例1，n=3时：1—>3；2—>3；1—>2—>3，合计3种路线。 样例2，n=4时：1—>2—>4；2—>4；1—>3—>4；2—>3—>4；1—>2—>3—>4，合计5种路线。

来源

童程童美