整数划分

问题描述

• 将正整数n表示成一系列正整数的和，n=n1+n2+…+nk，返回划分的方法数。
• 比如6的整数划分为11种。

最大数	整数划分
6	6
5	5+1
4	4+2,4+1+1
3	3+3,3+2+1,3+1+1+1
2	2+2+2,2+2+1+1,2+1+1+1+1
1	1+1+1+1+1+1

算法分析

• 将正整数n表示成一系列正整数之和， n=n1+n2+......+nk，其中n1>=n2>=......nk,k>=1，正整数的这种划分称为正整数n的划分，正整数n的不同划分的个数称为正整数n的划分数。

代码实现

流程图

public class Solution {

    public static void main(String[] args) {
        int i = 20;
        int partNum;
        partNum = new Solution().intPart(i, i);
        System.out.println(i + "的整数划分数为：" + partNum);
    }

    public int intPart(int n, int m) {
        if ((n < 1) || (m < 1)) return 0;
        if ((n == 1) || (m == 1)) return 1;
        if (n < m) return intPart(n, n);
        if (n == m) return intPart(n, m - 1) + 1;
        return intPart(n, m - 1) + intPart(n - m, m);
    }
}

• intPart(int n ,int m)：对整数n进行整数划分，其中m为整数划分中的最大数，返回划分数，所以intPart(n,n)表示n的所有整数划分数。
• 根据n和m的关系，考虑以下几种情况：
  • 当n=1时，不论m的值为多少（m>0)，只有一种划分即{1};
  • 当m=1时，不论n的值为多少，只有一种划分即n个1, {1,1,1,…,1}
  • 当n=m时，根据划分中是否包含n，可以分为两种情况：
    • 划分中包含n的情况，只有一个即{n}
    • 划分中不包含n的情况，这时划分中最大的数字也一定比n小，即n的所有（n-1）划分。
    • 因此 f(n,n) =1 + f(n,n-1)
  • 当n<m时，由于划分中不可能出现负数，因此就相当于f(n,n)
  • 但n>m时，根据划分中是否包含最大值m，可以分为两种情况：
    • 划分中包含m的情况，即{m, {x1,x2,…xi}}，其中{x1,x2,… xi} 的和为n-m，因此这情况下为f(n-m,m)
    • 划分中不包含m的情况，则划分中所有值都比m小，即n的（m-1）划分，个数为f(n,m-1)
    • 因此 f(n, m) = f(n-m, m)+f(n,m-1)