本文共 4079 字，大约阅读时间需要 13 分钟。

[编程题]: 整数拆分问题

给定一个整数n，将n拆分，问一共有多少种拆分方法。

整数拆分是很经典的问题。也是很经典的 “动态规划” 问题。

问题分析

1 = 12 = 2   = 1 + 1  3 = 3   = 2 + 1   = 1 + 1 + 1  4 = 4   = 3 + 1   = 2 + 2   = 2 + 1 + 1   = 1 + 1 + 1 + 1 + 1  5 = 5   = 4 + 1    = 3 + 2   = 3 + 1 + 1   = 2 + 2 + 1   = 2 + 1 + 1 + 1   = 1 + 1 + 1 + 1 + 1   6 = 6  = 5 + 1  = 4 + 2  = 4 + 1 + 1  = 3 + 3  = 3 + 2 + 1  = 3 + 1 + 1 + 1  = 2 + 2 + 2  = 2 + 2 + 1 + 1  = 2 + 1 + 1 + 1 + 1  = 1 + 1 + 1 + 1 + 1 + 1.......

1. 递归方法

若设f(n, m)表示将n拆分，拆分得到的序列中最大值不超过m.

求解f(n, m)分为如下几种情况：

• n == 1 或者 m == 1
  • n == 1, 即待拆分的n为1，只能拆分为 {1}
  • m == 1, 即拆分n得到的序列最大值为1，那么这个拆分得到的序列只能为{1, 1, 1, …, 1}，n个1
• 其他情况：
  1. n == m
     n == m时，分为两种情况：
     1.1 拆分得到的序列包含m，即序列只包含一个n —— {n}，拆分结束
     1.2 拆分得到的序列不包含m，即序列{m, {…}}，后面的拆分序列为子问题 f(n - m, m)
     综上：n == m时的拆分方案共有：1 + f(n - m, m)
  2. n < m
     n < m时，拆分的方案共有: f(n, n)
     因为 拆分不能拆分出负数出来，拆分得到的最大值只能为n，因此转移到f(n, n).
  3. n > m
     n > m时的拆分，也分为两种情况：
     3.1 拆分得到的序列包含m，那么待拆分的数就为n - m，下一次可以拆分得到的最大值仍为m，因此转移到f(n - m, m);
     3.2 拆分得到的序列不包含m，那么待拆分的数还是n，下一次可以拆分得到的最大值变为了m - 1 (本次拆分不包含m，下一次也肯定就不会包含m了)

代码

public static int f(int n, int m) {      if (n == 1 || m == 1) {          return 1;   } else {          if (n == m) {              return 1 + f(n, m - 1);       }       else if (n < m) {              return f(n, n);       }       else {              return f(n - m, m) + f(n, m - 1);       }   }}

如果要得到所有的拆分序列，则在拆分过程中保存下来拆分结果。

public static int f(int n, int m, List
   
     one, List
    
     
      > res) {       if (n == 1 || m == 1) {           if (n == 1) {               one.add(1);            res.add(new ArrayList<>(one));            one.remove(one.size() - 1);        } else {               for (int i = 1; i <= n; i++) one.add(1);            res.add(new ArrayList<>(one));            for (int i = 1; i <= n; i++) one.remove(one.size() - 1);        }        return 1;    } else {           if (n == m) {               one.add(m);            res.add(new ArrayList<>(one));            one.remove(one.size() - 1);            return 1 + f(n, m - 1, one, res);        }        else if (n < m) {               return f(n, n, one, res);        }        else {               one.add(m);            int ans1 = f(n - m, m, one, res);            one.remove(one.size() - 1);            int ans2 = f(n, m - 1, one, res);            return ans1 + ans2;        }    }}
     
    
   

得到的拆分序列如下：

2. 动态规划方法

动态规划是在上面递归思路上的优化，减少了重复计算。

设 dp[n][m] 表示将 n 拆分，其中拆分得的最大的数不超过 m ；

• n == 1 或者 m == 1
  1. n == 1，只能拆分为{1}
  2. m == 1，只能拆分为{1, 1, …, 1}
• 其他
  1. n == m
     拆分包含m，即只能拆分为: {n}；拆分结束
     拆分不包含m，即转移为 dp[n][m - 1]
     综上，n == m时的转移方程为：
     dp[n][m] = 1 + dp[n][m - 1]
  2. n < m
     不可能拆分出负数，因此转移为 dp[n][n]
     即：dp[n][m] = dp[n][n]
  3. n > m
     也分为两种情况：
     拆分包含m，转移为dp[n - m][m];
     拆分不包含m，转移为dp[n][m - 1].
     综上，n < m时的转移方程为：
     dp[n][m] = dp[n - m][n] + dp[n][m - 1]

代码

public class Main {   	public static void main(String[] args) {           Scanner input = new Scanner(System.in);        while (input.hasNext()) {               int n = input.nextInt();            int[][] dp = new int[n + 1][n + 1];            for (int i = 1; i < n + 1; i++) {                   for (int j = 1; j < n + 1; j++) {                       if (i == 1 || j == 1) {                           dp[i][j] = 1;                    } else {                           if (i == j) {                               dp[i][j] = dp[i][j - 1] + 1;                        } else if (i < j) {                               dp[i][j] = dp[i][i];                        } else {                               dp[i][j] = dp[i - j][j] + dp[i][j - 1];                        }                    }                    System.out.print(dp[i][j] + " ");                }                System.out.println();            }            System.out.println("res = " + dp[n][n]);        }    }}

相关的改编

• n == 1 或者 m == 1
  1. n == 1，只能拆分为{1}
  2. m == 1，只能拆分为{1, 1, …, 1}
• 其他
  1. n == m
     拆分不能包含n自身，因此这里的拆分必须转移到dp[n][m - 1]，拆分结束条件必须为
     综上，n == m时的转移方程为：
     dp[n][m] = 1 + dp[n][m - 1]
  2. n < m
     不可能拆分出负数，因此转移为 dp[n][n]
     即：dp[n][m] = dp[n][n]
  3. n > m
     也分为两种情况：
     拆分包含m，转移为dp[n - m][m];
     拆分不包含m，转移为dp[n][m - 1].
     综上，n < m时的转移方程为：
     dp[n][m] = dp[n - m][n] + dp[n][m - 1]