将一个正整数n表示成一系列正整数之和。
n = n1+n2+n3+...+ni(其中,n1>=n2>=...>=nk>=1,k>=1)
正整数n的一个这种表示称为正整数n的一个划分。正整数n的不同的划分个数称为正整数n的划分数,记作p(n)。
例如:正整数6有如下11种不同的划分,所以p(6) = 11。
6;
5+1;
4+2,4+1+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。
求正整数n的不同划分个数。
正整数n要怎么分呢。将n划分成最大加数n1<= m的划分个数记为f(n, m)
一、 递归的做法:
最后一点:
n>m>1时,根据划分中是否包含最大值m,可以分为两种情况:
1)划分中包含m的情况,即{m, {m+1,m+2...m+i}}, 其中{m+1,m+2,..m+i} 的和为n-m,因此这情况下为理解为n-m不大于m的划分,个数为q(n-m,m);
2)划分中不包含m的情况,那么划分出来的正整数都比m小,最大的为m-1,即为n的(m-1)划分,那么,此时这种情况的个数为q(n,m-1);所以,综合上面两点 q(n, m) = q(n-m, m)+q(n,m-1);
原文链接:https://blog.csdn.net/weixin_35909255/article/details/54896972
int f(int n, int m){
if(n < 1 || m < 1) return 0;
if(n == 1 || m == 1) return 1;
if(n < m) return f(n,n);
if(n == m) return 1+f(n, n-1);
return f(n-m,m) + f(n,m-1);
}