整数划分问题

发表于 更新于 分类于 ，
本文字数： 777

整数划分问题思路简记

问题

  • 将 m 个苹果放入 n 个盘子，问一共有几种放法（2，1，1与1，2，1被视为同一种放法）
  • 将整数 m 划分为若干个整数相加，问一共有几种分法（2，1，1与1，2，1被视为同一种分法）
  • ········

诸如此类问题，可以通过递归实现求解步骤

思路

m 为划分数，n 称为最大划分数（划分出来的数字最大值）

递归过程中

  1. 当 m = 1 或者 n = 1 时，只有一种划分方法
  2. 当 m < n 时，相当于最大划分数为 m
  3. 当 m = n 时，划分数中存在 n 的划分方法只有一种情况，所以为最大划分数为 n - 1 的分法数加一
  4. 当 m > n 时（一般情况）可以分为两种情况
    • 划分的数中不存在 n 这个数字，即最大划分数为 n - 1 的情况
    • 划分的数中存在 n 这个数字，则余下的数为 m - n，对 m - n 进行划分（递归实现）

放苹果也是同样的道理 m 为苹果数，n 为最大可放盘子数 递归过程中

  1. 当 m = 1 或者 n = 1 时，苹果或者盘子只有一个，只有一种划分方法
  2. 当 m < n 时，盘子比苹果多，忽略多余的盘子（砸碎）
  3. 当 m = n 时，每个盘子只有一个苹果的情况只有一种放法，所以为一般情况下空一个盘子放法数加一
  4. 当 m > n 时（一般情况）可以分为两种情况
    • 先在 n 个盘子中放一个苹果，不留空盘子，然后再放余下的 m - n 个苹果
    • 空一个盘子，在 n - 1 个盘子里放 m 个苹果

代码（采用了记忆化递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int app(int m, int n)
{
    if (a[m][n])
        return a[m][n];
    else
    {
        if (m == 1  n == 1)
            return a[m][n] = 1;
        else if (n > m)
            return a[m][n] = app(m, m);
        else if (n == m)
            return a[m][n] = app(m, n - 1) + 1;
        else
            return a[m][n] = app(m - n, n) + app(m, n - 1);
    }
}