整数划分问题

整数划分问题是算法中的一个经典命题之一，有关这个问题的讲述在讲解到递归时基本都将涉及。
所谓整数划分，是指把一个正整数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的关系，考虑以下几种情况：

1. 当n=1时，不论m的值为多少（m>0)，只有一种划分即{1};

2. 当m=1时，不论n的值为多少，只有一种划分即n个1，{1,1,1,…,1};

3. 当n=m时，根据划分中是否包含n，可以分为两种情况：
   (1) 划分中包含n的情况，只有一个即{n}；
   (2) 划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有(n-1)划分。
   因此 f(n,n) =1 + f(n,n-1);

4. 当n<m时，由于划分中不可能出现负数，因此就相当于f(n,n);

5. 但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) + " 毫秒");
        }
    }
}