整数划分是把一个正整数 N 拆分成一组数相加并且等于 N 的问题.
比如:
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
假设F(N,M) 整数 N 的划分个数,其中 M 表示将 N 拆分后的序列中最大数
考虑边界状态:
M = 1 或者 N = 1 只有一个划分 既: F(1,1) = 1
M = N : 等于把M - 1 的划分数加 1 既: F(N,N) = F(N,N-1) + 1
M > N: 按理说,N 划分后的序列中最大数是不会超过 N 的,所以 F(N,M ) = F(N,N)
M < N: 这个是最常见的, 他应该是序列中最大数为 M-1 的划分和 N-M 的划分之和, 比如F(6,4),上面例子第三行, 他应该等于对整数 3 的划分, 然后加上 2 的划分(6-4) 所以 F(N,M) = F(N, M-1) + F(N-M,M)
整数划分问题
数 n 的划分是将 n 表示成多个正整数之和的形式
划分可以分为两种情况：
A 划分的多个正整数中，正整数的数量是任意的
这又可以分为划分的正整数中，正整数可以相同与不同两类
1. 划分的多个正整数可以相同, 递推方程可以表示为：
(1) dp[n][m]= dp[n][m-1]+ dp[n-m][m]
dp[n][m]表示整数 n 的划分中，每个数不大于 m 的划分数。
则划分数可以分为两种情况:
a. 划分中每个数都小于 m， 相当于每个数不大于 m- 1, 故
划分数为 dp[n][m-1].
b. 划分中有一个数为 m. 那就在 n中减去 m , 剩下的就相当
于把 n-m 进行划分， 故划分数为 dp[n-m][m];
(2) dp[n][m]= dp[n][m+1]+ dp[n-m][m]
dp[n][m]表示整数 n 的划分中，每个数不小于 m 的划分数。
同理可证明该式。
2. 划分的多个正整数互不相同，递推方程可以表示为：
(1) dp[n][m]= dp[n][m-1]+ dp[n-m][m-1]
dp[n][m]表示整数 n 的划分中，每个数不大于 m 的划分数。
同样划分情况分为两种情况：
a. 划分中每个数都小于 m, 相当于每个数不大于 m- 1,
划分数为 dp[n][m-1].
b. 划分中有一个数为 m. 在 n 中减去 m, 剩下相当对
n- m 进行划分，并且每一个数不大于 m- 1，故划分数
为 dp[n-m][m-1]
(2) dp[n][m]= dp[n][m+1]+ dp[n-m][m]
dp[n][m]表示整数 n 的划分中，每个数不小于 m 的划分数。
B 划分的多个正整数中，正整数的数量是固定的
把一个整数 n 无序划分成 k 份互不相同的正整数之和的方法总数。
方程为：
dp[n][k]= dp[n-k][k]+ dp[n-1][k-1];
证明方法参考： http://www.mydrs.org/program/html/0369.htm
另一种理解，总方法可以分为两类：
第一类: n 份中不包含 1 的分法，为保证每份都 >= 2，可以先拿出 k 个 1 分
到每一份，然后再把剩下的 n- k 分成 k 份即可，分法有: dp[n-k][k]
第二类: n 份中至少有一份为 1 的分法，可以先那出一个 1 作为单独的1份，剩
下的 n- 1 再分成 k- 1 份即可，分法有：dp[n-1][k-1]
相关习题：
http://acm.hit.edu.cn/ojs/show.php?Proid=1402&Contestid=0
http://acm.hnu.cn:8080/online/?action=problem&type=show&id=11299&courseid=0
#include<iostream>
#include<stdio.h>
using namespace std;
int dp[4505][4505];
int solve(int n,int m)
{
int i,j;
for(i=1;i<=n;++i)
{
dp[i][0]=0;
for(j=1;j<=m;++j)
{
dp[0][j]=0;
if(i>=j)
dp[i][j]=dp[j-1][j]+1;
else
{
dp[i][j]=dp[i-1][j]+dp[i][j-i];
if(dp[i][j]>=1000000007)
dp[i][j]-=1000000007;
}
}
}
return dp[n][m];
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
printf("%d\n",solve(n,m));
return 0;
}类似问题：M个小球装N个盒子，或者苹果装盘问题
把M个球放到N个盒子,允许有空的盒子(不放球),有多少种放法?
典型的DP问题:
用F(m,n)表示有多少种放法:
如果m=0 或者 m=1 , F = 1
如果n=0 或者 n=1 , F =1
既F(0,0) = F(0,1) = F(1,0) = F(1,1) = 1
否则 F = F(m-n,n) + F(m,n-1)这就是DP的解空间递归解
每一次DP应用,都是一次创造
#include <stdio.h>
int F(int m,int n);
int main()
{
int m;
int n;
int f;
printf("Intput the number of M and N \n");
scanf("%d %d",&m,&n);
f = F(m,n);
printf("There are total %d methods\n\n",f);
};
int F(int m,int n)
{
if(m==0||m==1) return 1;
if(n==0||n==1) return 1;
if(m<n) return F(m,m);
else return F(m-n,n)+F(m,n-1);
};
三、关于整数的质因子和分解
【问题描述】
歌德巴赫猜想说任何一个不小于6的偶数都可以分解为两个奇素数之和。对此问题扩展，如果一个整数能够表示成两个或多个素数之和，则得到一个素数和分解式。对于一个给定的整数，输出所有这种素数和分解式。注意，对于同构的分解只输出一次（比如5只有一个分解2 + 3，而3 + 2是2 + 3的同构分解式）。
例如，对于整数8，可以作为如下三种分解：
(1) 8 = 2 + 2 + 2 + 2
(2) 8 = 2 + 3 + 3
(3) 8 = 3 + 5
【算法分析】
由于要将指定整数N分解为素数之和，则首先需要计算出该整数N内的所有素数，然后递归求解所有素数和分解即可。
C++代码实现如下：
#include <iostream>
#include <vector>
#include <iterator>
#include <cmath>
using namespace std;
// 计算num内的所有素数（不包括num）
void CalcPrimes(int num, vector<int> &primes)
{
primes.clear();
if (num <= 2)
return;
primes.push_back(2);
for (int i = 3; i < num; i += 2)
{
int root = int(sqrt(i));
int j = 2;
for (j = 2; j <= root; ++j)
{
if (i % j == 0)
break;
}
if (j > root)
primes.push_back(i);
}
}
// 输出所有素数组合(递归实现)
int PrintCombinations(int num, const vector<int> &primes, int from, vector<int> &numbers)
{
if (num == 0)
{
cout << "Found: ";
copy(numbers.begin(), numbers.end(), ostream_iterator<int>(cout, " "));
cout << '\n';
return 1;
}
int count = 0;
// 从第from个素数搜索，从而避免输出同构的多个组合
int primesNum = primes.size();
for (int i = from; i < primesNum; ++i)
{
if (num < primes[i])
break;
numbers.push_back(primes[i]);
count += PrintCombinations(num - primes[i], primes, i, numbers);
numbers.pop_back();
}
return count;
}
// 计算num的所有素数和分解
int ExpandedGoldbach(int num)
{
if (num <= 3)
return 0;
vector<int> primes;
CalcPrimes(num, primes);
vector<int> numbers;
return PrintCombinations(num, primes, 0, numbers);
}
int main()
{
for (int i = 1; i <= 20; ++i)
{
cout << "When i = " << i << ":\n";
int count = ExpandedGoldbach(i);
cout << "Total: " << count << "\n\n";
}
}