数的划分，典型的DP问题。
题目要求：给定一个数n,要求输出这个数所有的划分的种数（不包括等分）。比如3=2+1，只有一种划分，1不能再分，2 不能分解成1+1,（就是说 数不能等分）
因此可以先考虑，将n分成K份的情况。那么所有的划分就可以是将n分成2，3,4,5，。。。n-1份之和，当然其中还需除去相等的情况。
参考博客：http://www.cnblogs.com/wanghetao/archive/2013/11/25/3442192.html
将n分解成k份，可以把问题转化为高中的排列组合问题：将n个小球，放在k个盒子里，要求盒子非空。那么可以转化为
1. 至少有一个盒子只有一个小球的情况数
+
2. 没有一个盒子只有一个小球的情况数
f[n][k]代表将n个小球放到k个盒子中且没有空盒的情况，那么
f[n][k] = f[n-1][k-1] + f[n-k][k]
f[n-1][k-1]则是至少有一个盒子只有一个小球，那么需要把剩余的n-1放到其余k-1个盒子中；
f[n-k][k]就是没有一个盒子只有一个小球，那么把k个球放到k个盒子中，剩余的n-k在分配到k个盒子中。
选择以上两种情况是因为以上两种情况比较容易写出表达式，而且以上对立两种情况的并集就是我们需要求的全集。（高中数学也是有用的啊。。。。）
根据上诉，写出一下代码：初始化 f[0][0] =0;f[i][1]=1;(i个球放到一个盒子 显然只有一种情况啦)
//输入一个数n 求出分成K份的分类数 public static int help(int n,int k){ int dp [][] = new int [91][91];//题目要求的数在1-90，90个数k等分 k也最多90; for(int i=0;i<dp.length;i++) dp[i][1] =1;//所有的数放到同一个盒子里 只有一种方法。 dp[0][0] =0; for(int i=1;i<=n;i++){ for(int j=1;j<=k&&j<=i;j++){ dp[i][j] = dp[i - 1][j - 1] + dp[i - j][j]; } } return dp[n][k]; }
现在，返回到我们开始的问题，将n划分，一共能划分成多少种？不包括等分情况也不能包括自身
那么只需要对划分的个数做一次遍历，将n分解成2,3,4,5，。。。。n-1;(不能等分，当然不能包括将n等分成n个1啦)
那么 如何排除其他等分情况，比如6=3+3=2+2+2， 9=3+3+3，只需验证n是否能被k整除即可，出去这种情况，就是不包含等分的情况
代码如下：
public class Main2 { public static void main(String args[]){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int count=0; for(int i=2;i<=n-1;i++){ if(n%i!=0) count+=help(n,i); else if(n%i==0){ count+=help(n,i); count-=1; } } System.out.println(count); } }
以上就是数组划分的一部分内容。
当然，还有变式，比如说：划分成奇数，偶数，等。下一篇博客再总结一下。