1847 - 【基础】摆动序列-大脑图图OJ

题目描述

如果一个序列满足下面的性质，我们就将它称为摆动序列：

序列中的所有数都是不大于 $k$ 的正整数；
序列中至少有两个数。
序列中的数两两不相等；
如果第 $i-1$ 个数比第 $i-2$ 个数大，则第 $i$ 个数比第 $i-2$ 个数小；如果第 $i-1$ 个数比第 $i-2$ 个数小，则第 $i$ 个数比第 $i-2$ 个数大。

比如，当 $k=3$ 时，有下面几个这样的序列：

一共有 $8$ 种，给定 $k$ ，请求出满足上面要求的序列的个数。

输入

输入包含了一个整数 $k$ 。（ $k \leq 20$ ）

输出

输出一个整数，表示满足要求的序列个数。

样例

说明

【来源】蓝桥杯算法训练

来源

蓝桥杯递推

标签

题目参数

统计

上一题下一题