整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时基本都将涉及。
所谓整数划分，是指把一个正整数n写成如下形式：
n=m1+m2+…+mi; （其中mi为正整数，并且1 <= mi <= n），则{m1,m2,…,mi}为n的一个划分。
如果{m1,m2,…,mi}中的最大值不超过m，即max(m1,m2,…,mi)<=m，则称它属于n的一个m划分。这里我们记n的m划分的个数为f(n,m);
例如但n=4时，他有5个划分，{4},{3,1},{2,2},{2,1,1},{1,1,1,1};
注意4=1+3 和 4=3+1被认为是同一个划分。
该问题是求出n的所有划分个数，即f(n, n)。下面我们考虑求f(n,m)的方法;
根据n和m的关系，考虑以下几种情况：
当n=1时，不论m的值为多少（m>0)，只有一种划分即{1};
当m=1时，不论n的值为多少，只有一种划分即n个1，{1,1,1,…,1};
当n=m时，根据划分中是否包含n，可以分为两种情况：
(1) 划分中包含n的情况，只有一个即{n}；
(2) 划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有(n-1)划分。
因此 f(n,n) =1 + f(n,n-1);当n<m时，由于划分中不可能出现负数，因此就相当于f(n,n);
但n>m时，根据划分中是否包含最大值m，可以分为两种情况：
(1) 划分中包含m的情况，即{m, {x1,x2,…xi}}, 其中{x1,x2,… xi} 的和为n-m，可能再次出现m，因此是（n-m）的m划分，因此这种划分
个数为f(n-m, m);
(2) 划分中不包含m的情况，则划分中所有值都比m小，即n的(m-1)划分，个数为f(n,m-1);
因此 f(n, m) = f(n-m, m)+f(n,m-1);
综合以上情况，我们可以看出，上面的结论具有递归定义特征，其中（1）和（2）属于回归条件，（3）和（4）属于特殊情况，将会转换为情况（5）。而情况（5）为通用情况，属于递推的方法，其本质主要是通过减小m以达到回归条件，从而解决问题。其递推表达式如下：
f(n, m)= 1; (n=1 or m=1)
f(n, n); (n<m)
1+ f(n, m-1); (n=m)
f(n-m,m)+f(n,m-1); (n>m)
递归代码
import java.util.Scanner;
/**
* Created by EthanWalker on 2017/11/19.
*/
public class IntPartition {
public static int digui(int n, int m) {
if(n==0||m==0) return 0;
if (n == 1 || m == 1) return 1;
if (n == m) return 1 + digui(n, n - 1);
if (n < m) return digui(n, n);
// n>m 时
return digui(n - m, m) + digui(n, m - 1);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (true) {
int i = scanner.nextInt();
if (i == -1) {
break;
}
long begin = System.currentTimeMillis();
int digui = digui(i, i); //递归超时
long end = System.currentTimeMillis();
System.out.println("递归的结果： " + digui);
System.out.println("花费的时间: "+(end-begin)+" 毫秒");
}
}
}
非递归(二维数组)
import java.util.Scanner;
/**
* Created by EthanWalker on 2017/11/19.
*/
public class IntPartitionArray {
public static int array(int n) {
int[][] a = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
a[i][j] = 0;
}
}
for (int i = 1; i <= n; i++) {
a[i][1] = 1;
a[1][i] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (j == 1 || i == 1) a[i][j] = 1;
else if (i == j) {
a[i][j] = 1 + a[i][i - 1];
} else if (i < j) {
a[i][j] = a[i][i];
} else if (i > j) {
a[i][j] = a[i - j][j] + a[i][j - 1];
}
}
}
return a[n][n];
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[][] a = new int[121][121];
for (int i = 0; i <= 120; i++) {
for (int j = 0; j <= 120; j++) {
a[i][j] = 0;
}
}
for (int i = 1; i <= 120; i++) {
a[i][1] = 1;
a[1][i] = 1;
}
for (int i = 1; i <= 120; i++) {
for (int j = 1; j <= 120; j++) {
if (j == 1 || i == 1) a[i][j] = 1;
else if (i == j) {
a[i][j] = 1 + a[i][i - 1];
} else if (i < j) {
a[i][j] = a[i][i];
} else if (i > j) {
a[i][j] = a[i - j][j] + a[i][j - 1];
}
}
}
while (scanner.hasNext()) {
int i = scanner.nextInt();
// long begin = System.currentTimeMillis();
int array =a[i][i];
// long end = System.currentTimeMillis();
System.out.println(array);
// System.out.println("数组计算的结果: " + array);
// System.out.println("花费的时间: " + (end - begin) + " 毫秒");
}
}
}
