小慕正在完成一个登山项目,途中遇到一段有 n 级台阶的阶梯。不过小慕有一个习惯,每次只前进 1 步或 3 步。 请问小慕通过这段阶梯有多少种不同的前进方式。
提示:带虚线的词点一下有通俗解释。
输入描述
输入只有一个数 n, 0 <= n <= 50,代表此阶梯有多个台阶。
输出描述
一个整数,表示有多少种跳跃方式。
示例
示例 1
输入
50
输出
122106097
示例 2
输入
3
输出
2
时间限制 1000 ms · 内存限制 128 MB
小慕正在完成一个登山项目,途中遇到一段有 n 级台阶的阶梯。不过小慕有一个习惯,每次只前进 1 步或 3 步。 请问小慕通过这段阶梯有多少种不同的前进方式。
提示:带虚线的词点一下有通俗解释。
输入只有一个数 n, 0 <= n <= 50,代表此阶梯有多个台阶。
一个整数,表示有多少种跳跃方式。
示例 1
输入
50
输出
122106097
示例 2
输入
3
输出
2
时间限制 1000 ms · 内存限制 128 MB