整数拆分的两种方法——递归和dp

首先来了解整数拆分的创始人——拉马努金。

这位是我数学上最佩服的几个大神之一，当然最佩服的还是欧拉，欧了～

如果提前了解了离散数学里的集合划分知识，那下面内容会更加易懂。

问题描述： 有一个正整数n，可以拆分成最大数为m的的拆分方案，要求所有的方案都不重复。 例如n = 4， m = 4，拆分方案如下： 4 = 4； 4 = 1 + 3； 4 = 2 + 2； 4 = 1 + 2 + 1； 4 = 1 + 1 + 1 + 1；

首先，我们先假设n和m的大小。

  1. n = 1，m>0；则f(n,m) = 1，即{1};
  2. n > 0，m = 1；则f(n,m) = 1，即{1, 1, 1, 1, …};
  3. n < m；f(n, m) = f(n, n);
  4. n = m； (1)n的划分包含m时，则f(n,m) = 1，即{m}; (2)n的划分不包含m时，则f(n,m) = f(n, m -1)，即{n1, n2, n3…..}; 即n = m时，f(n, m) = f(n, m - 1) + 1；
  5. n > m； (1)n的划分包含m时，则f(n,m) = f(n - m, m), 即{m, n1, n2,….}，其中n1 + n2 + …. = n - m，其中可能还会出现m； (2)n的划分不包含m时，则f(n, m) = f(n, m - 1); 即n > m时，f(n, m) = f(n, m - 1) + f(n - m, m)；

流程图为：

递归法

1
2
3
4
5
6
7
8
9
10
11
ll PartitionCount(ll n, ll m)
{
    if(n == 1  m == 1)
        return 1;
    else if(n < m)
        return PartitionCount(n , n);
    else if(n == m)
        return PartitionCount(n , n - 1) + 1;
    else
        return PartitionCount(n - m , m) + PartitionCount(n , m - 1);
}

由于递归法可能会重复计算，耗时方面会巨大，所以就有下面的动态规划。

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ll dp[10005][10005];

void Partition_DP(ll n, ll m)
{
    for(ll i = 1;i <= n + 1; i++)
    {
        for(ll j = 1;j <= m + 1; j++)
        {
            if(i == 1  j == 1)
                dp[i][j] = 1;
            else if(i == j)
                dp[i][j] = 1 + dp[i][j - 1];
            else if(i < j)
                dp[i][j] = dp[i][i];
            else
                dp[i][j] = dp[i - j][j] + dp[i][j - 1];
        }
    }
}

整数拆分和排列组合息息相关，排列组合里的隔板法就和这个非常像，但是到该用的时候就不会用了…

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/05/20/integer-splitting/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！