NYOJ 90 —— 求正整数n划分为若干个正整数的划分个数

整数划分

时间限制：3000 ms  |  内存限制：65535 KB

描述

将正整数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。 

输入

第一行是测试数据的数目M（1<=M<=10）。以下每行均包含一个整数n（1<=n<=10）。

输出

输出每组测试数据有多少种分法。

样例输入

1
6

样例输出

11



下面转自博客：http://www.cnblogs.com/hoodlum1980/archive/2008/10/11/1308493.html

　　所谓整数划分，是指把一个正整数n写成如下形式：

　　　　n=m₁+m₂+...+m_i; （其中m_i为正整数，并且1 <= m_i <= n），则：{m₁,m₂,...,m_i}为n的一个划分。

　　如果{m₁,m₂,...,m_i}中的最大值不超过m，即max(m1,m2,...,mi)≤m，则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);

　　例如：当n=4时，共有5个划分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};

　　注意4=1+3 和 4=3+1被认为是同一个划分。

　　该问题是求出n的所有划分个数，即f(n, n)。

　　通用的递推公式如下：

　　 　　 f(n, m)    =    1;                                        ( n = 1 or m = 1 )

                           　　 f(n, n);                                 ( n < m )

                            　　1+ f(n, m - 1);                      ( n = m )

                            　　f(n - m, m) + f(n, m - 1);       ( n > m )

1）自顶向下实现的版本：

#include 
#include using namespace std;int f(int i, int j)
{if(i==1 || j==1)    return 1;if(ireturn f(i, i);if(i==j)    return f(i, i-1) + 1;return f(i, j-1) + f(i-j, j);    
}int main ()
{int T, n;scanf("%d", &T);while(T--) {scanf("%d", &n);printf("%d
", f(n, n));    }return 0;
}

 

2）自底向上实现的版本：

#include 
#include using namespace std;const int MAXN = 15;int dp[MAXN][MAXN];void init()
{for(int i=1; i) {for(int j=1; j) {if(j>i)    dp[i][j] = dp[i][i];else if(j == i)    dp[i][j] = dp[i][j-1] + 1;else    dp[i][j] = dp[i][j-1] + dp[i-j][j];}}
}int main ()
{init();int T, n;scanf("%d", &T);while(T--) {scanf("%d", &n);printf("%d
", dp[n][n]);}return 0;
}