【算法基础】整数划分问题

【问题】将整数n表示为一系列正整数的和。

n = n1 + n2 + ...+ nk (n1 >= n2>=......>=nk>=1,k>=1) 

并称之为n的划分。不同的划分个数称为正整数n的划分数，p(n)

建立如下递归关系：

在不同的划分中，将最大的加数n1不大于m的划分数计做q(n,m)

1.q(n,1) = 1,n >= 1;表示，最大加数小于等于1，就是，n1<=1.而n1>=1,因此n1 = 1，该种类型划分只有一种。

2,q(n,m) = q(n,n),m>=n;因此，m >=n > n1. 对于数字m和n他们划分的最大加数，都不会比n大，就说明划分数相同。

3.q(n,n) = 1 + q(n,n-1);n的划分由n1 = n,和n1 <= n-1构成。

4.q(n,m) = q(n,m-1) + q(n-m,m),n > m > 1;

n的最大划分数n1不大于m的划分数（n1 <= m）由，n1 = m和n1 <= m-1构成。

n1 = m,则n2 + n3 + ...+nk = n - m,在对n-m中找到最大为m的划分。表示为q(n-m,m);

n1 <= m - 1,表为q(n,m-1)

扩展：

【输入】标准的输入包含若干组测试数据。每组测试数据是一行输入数据,包括两个整数N 和 K。 

(0 < N <= 50, 0 < K <= N)

【输出】

对于每组测试数据，输出以下三行数据: 

第一行: N划分成K个正整数之和的划分数目 

第二行: N划分成若干个不同正整数之和的划分数目 

第三行: N划分成若干个奇正整数之和的划分数目

分析：

分为不同正整数包含：

1.n1 <= m -1 ,q(n,m-1)

2.n1 = m;在从n-m中找到最大为加数为m-1的划分。q(n-m,m-1)

q(n,m) = q(n,m-1) + q(n-m,m-1),分为若干不同数的划分数。

分为K个正整数的划分数：

设置f(n,k)表示为k个数的n的划分。

1.k个数中包含1：其余k-1个数去分n-1的划分。f(n-1,k-1)

2.k个数不包含1：每个数都比1大，k个数都分一个1.其余的n - k在分到k个数中的划分数。f(n - k,k)

f(n,k) = f(n - 1,k-1) + f(n - k,k)

分为若干个奇整数的和：

设置x(i,j),数字i划分为j个奇数的划分数，y(i,j)数字i划分为j个偶数的划分数。

1.包含1：减掉1后，i-1需要分配到j-1个奇数中，x(i-1,j-1)

2.不包含1：对j个奇数都减去1后，就是i-j的j个偶数的划分。y(i-j,j)

x(i,j) = x(i - 1,j-1) + y(i-j,j)

或：

1.m奇数。包含m:q(n -m,m),不包含m，q(n,m-1) ;q(n,m) = q(n -m,m) + q(n,m-1)

2.m偶数。q(n,m) = q(n,m-1)