h269. 非降整数拆分

题目描述

把正整数 $n$ 写成一个或多个正整数之和，并要求各个加数从左到右非降。例如，$4$ 的一种拆分是 $1+1+2$。

只要加数序列不同，就视为不同方案；由于要求非降，改变相同加数的排列不会产生新方案。请统计方案总数，其中也包含只写一个 $n$ 的方案。

输入格式

输入一个整数 $n$。

输出格式

输出非降整数拆分的方案数。

数据范围

• $1\le n\le 30$
• 答案不超过 $5604$。

样例

输入

5

输出

7

标签：递归、回溯、整数拆分