1009. 整数的拆分

单点时限: 2.0 sec

内存限制: 256 MB

将正整数 n 表示成一系列正整数之和 : n=n1+n2+…+nk,其中 n1≥n2≥…≥nk≥1(k≥1)

正整数 n 的这种表示称为正整数 n 的拆分。求正整数 n 的不同拆分个数。

例如,正整数 6 有如下 11 种不同的拆分 :

6;

5+1;

4+2,4+1+1;

3+3,3+2+1,3+1+1+1;

2+2+2,2+2+1+1,2+1+1+1+1;

1+1+1+1+1+1。

例如,正整数 3 有如下 3 种不同的拆分 :

3;

2+1;

1+1+1。

输入格式

本题有多组测试数据,每组一行,每行有一个正整数 N(1<=N<=100)

输出格式

每组测试数据输出一行,表示有多少种拆分方法

样例

Input
1
3
5
Output
1
3
7

393 人解决,637 人已尝试。

531 份提交通过,共有 1706 份提交。

5.8 EMB 奖励。

创建: 14 年,2 月前.

修改: 1 年,6 月前.

最后提交: 4 小时前.

来源: N/A

题目标签
DP