整数划分问题

将一个整数划分为多个整数想加的形式，并计算划分方法。
例：6的划分：
6=5+1
6=4+2
6=4+1+1
6=3+3
6=3+2+1
6=3+1+1+1
6=2+2+2
6=2+2+1+1
6=2+1+1+1+1
6=1+1+1+1+1+1

问题分析

这个问题显然要构造递归关系来解决，碰到这个问题时，我们很容易知道当一个整数被分为都是1时，这时应该已经完成了整个递归的过程。如果你已经发现了这一出口，那我们就开始对划分的方式进行分类。
笔者这里分为两类：

第一类	第二类
6=5+1	6=3+3
6=4+2	6=2+2+2
6=4+1+1
6=3+2+1
6=3+1+1+1
6=2+2+1+1
6=2+1+1+1+1
6=1+1+1+1+1+1

我这里就简单的使用是否含有1作为界限，当然也可以使用别的界限，只不过递归的形式就不同了。给定一个整数N,M是N中不超过N的最大整数。
第一类就可以写成F(N,M-1)，第二类写成F(N-M,M)，即递归表达式
F(N,M)=F(N,M-1)+F(N-M,M)

public static int divInt(int n,int m){
         if (m == 1) return 1;
         if (n <= m) return 1 + divInt(n, n - 1);
         if (m > 1) return divInt(n, m - 1) + divInt(n - m, m);
        return 0;
    } 

转载于:https://www.jianshu.com/p/a0203ce4f362