本文是以下博客文章在适当优化组合后的转载集合
http://blog.csdn.net/chenhuajie123/article/details/11990827
http://www.cnblogs.com/xiaoxian1369/archive/2011/09/12/2174212.html
以及 Roly Yu在第二篇文章的评论
1.将n划分成不大于m的划分法：
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-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.将n划分成k个数的划分法：
dp[n][k]= dp[n-k][k]+ dp[n-1][k-1];
方法可以分为两类：
第一类: 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]
3.将n划分成若干奇数的划分法：
g[i][j]:将i划分为j个偶数；f[i][j]:将i划分为j个奇数
g[i][j] = f[i - j][j];
f[i][j] = f[i - 1][j - 1] + g[i - j][j];
方法可以分为两类：
对于偶数f[i][j]: i 份中不包含 1 的分法，为保证每份都 >= 2，可以先拿出 j 个 1 分
到每一份，然后再把剩下的 i - j 分成 j 个奇数即可，分法有: g[i-j][j]
对于奇数g[i][j]: i 份中至少有一份为 1 的分法，可以先那出一个 1 作为单独的1份，剩
下的 n-1 再分成 j- 1 份即g[i - 1][j - 1],还有就是没有一份为 1 的分法可以先拿出 j 个 1 分
到每一份，然后再把剩下的i - j 分成 j 个偶数即f[i-j][j]，分法有：g[i-1][j-1] + f[i-j][j]
4.将正整数num划分成连续的正整数之和
输入数num，设置起始位置i，再遍历连续正整数的长度k，由公式计算出 sum = i + (i+1) + ... + (i+k) = (k+1) * (2*i + k) / 2，判断与n的关系，若相等则打印出从i到i+k这（k+1）个数；若 sum>num，则break；但很明显这算法的复杂度比较高！达到O（n^2）！因此我们需要找到一个更加优化的算法。
由上我们可知从i开始连续k个数之和的计算公式如下：sum = k * (2 * i + k - 1) / 2;
在题目要求sum == num 的所有可能情况，上面的解法是从起始位置开始循环，又根据连续个数循环，这样需要两重循环。但如果我们根据上面的公式逆向想想，如果sum==num时，i与k的关系等式为k * (2 * i + k - 1) = 2 * num。因此，如果用k循环，计算出起始位置 i = ( 2*n / k - k + 1) / 2，岂不是时间复杂度降到线性的了。
5.求划分因子乘积最大的一个划分及此乘积
问题简述：给定一个正整数n, 则在n所有的划分中, 求因子乘积最大的一个划分及此乘积。例如：8 = {8}, {7, 1}, {6, 2}, {5, 3}, {4, 4}, {3, 3, 2}, {2, 2, 2, 2} 等，那么在这些当中，3 * 3 * 2 的乘积最大，所以输出整个划分
和这个乘积 18。
算法分析：这是我在某个论坛上看到的问题，以及别人针对此问题的数学分析，现简单的整理如下：
(1)对于任意大于等于4的正整数m, 存在一个划分m = m1+m2, 使 m1*m2 >= m证: 令m1 = int(m/2), 则 m1 >= 2 ， m2 = m-m1; 那么m2 > 2，并且 m2 >= m/2 >= m1; m1*m2 >= 2*m2 >= m; 证毕;
该证明简单的来说就是：对于一个大于等于4的正整数m，存在一个2块划分的因子，这两个因子的乘积总是不小于原数m本身。
(2)由(1)知此数最终可以分解为 2^r * 3^s。现证明 r <= 2;
证：若r > 2, 则至少有3个因子为2, 而2*2*2 < 3*3;
所以可以将3个为2的因子,换为两个因子3；积更大；证毕。
综合(1)，(2)，则有：任何大于4的因子都可以有更好的分解, 而4可以分解为2*2。
所以：此数应该分解为 2^k1 * 3^k2。而且可以证明 k1>=0 并且 k1 <= 2，因此：
A.当n = 3*r 时, 分解为 3^r
B.当n = 3*r+1时, 分解为 3^(r-1)*2*2
C.当n = 3*r+2时, 分解为 3^r*2
剩下编程处理，那就是太简单了，首先是处理 <= 4的特殊情况，再对>4的情况进行模3的3种情况的判断，最后一一输出。
6.求把自然数num划分成互不相同的自然数的划分因子最大积
若1作划分数，显然最后的积并不会变大。又因为a*b>a+b(a>1&&b>1)，所以我们只需要设sum=2+3+...+n且sum刚好大于等于num（即sum-n<num)。
接下去的情况分三类：
1）num=sum n!为答案。
2）sum=num+1 则因数个数至少减少1个，为了使乘积最大，应去掉最小的2，并将最后一个数（最大）加上1。
3）sum>num+1 设k=sum-num，因为因数个数至少减少一个，为了使乘积最大，只需将等于k的数去掉即可。
- 还没有人评论，欢迎说说您的想法！
客服
