算法学习—整数划分

本文最后更新于 2025年2月23日 下午

🧮整数划分问题是一个较为常见的算法题，很多问题从整数划分这里出发，进行包装，形成新的题目，所以完全理解整数划分的解决思路对于之后的进一步学习算法是很有帮助的。

「整数划分」通常使用「动态规划」解决，本篇将记录如何使用动态规划分析和解决这个问题。

1. 问题描述📝

将正整数n表示成一系列正整数之和：n=n1+n2+…+nkn=n_1+n_2+…+n_k，其中n1≥n2≥…≥nk≥1，k≥1n_1 \geq n_2≥…≥n_k≥1，k≥1。正整数n的这种表示称为正整数n的划分，求正整数n的不同划分个数。

示例
正整数6有如下11种不同的划分：

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。

2. 动态规划简述💡

在使用动态规划解题之前，先简要回顾一下。

动态规划算法适用于求解最优化问题

如何判断这个问题能使用「动态规划」解决呢？ 主要看是否具有两个要素。

动态规划算法的基本要素

  1. 最优子结构性质

问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。

  1. 子问题重叠性质

递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。

2.1动态规划基本思想

动态规划算法与分治法类似，其基本思想是：将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。动态规划算法与分治法不同的是，经分解得到的子问题往往不是相互独立的，有大量子问题会重复出现。为了避免重复计算，动态规划法是用一个表来存放一计算过的子问题。

2.2 解题步骤

通常按四步骤设计动态规划算法：（1）找出最优解的性质，并刻画其结构特征；（2）递归定义求最优值的公式； ——（最为关键）（3）以自底向上方式计算最优值；（4）根据计算最优值时得到的信息，构造最优解。（看题目要求，有的题目不要求构造最优解）

接下来根据动态规划的思想，进行问题分析。

3. 问题分析🔍

3.1 明确问题的最优值和最优解

根据题意可知，最优值就是不同划分的个数

3.2 求递归定义最优值的公式

分析不同规模子问题之间的关系

在正整数n的所有不同划分中，将最大加数不大于m的划分个数记作q(n,m)，可以建立q(n,m)的如下递归关系：

  1. q(n,1)=1,n≥1;q(n,1)=1,n \geq 1;

    当最大加数m不大于1时，任何正整数n只有一种划分形式，即n=1+1+...+1⏞nn=\overset{n} {\overbrace{1+1+...+1}}

  2. q(n,m)=q(n,n),m≥n;q(n,m)=q(n,n),m \geq n;

    最大加数实际上不能大于n。

  3. q(n,n)=1+q(n,n−1);q(n,n)=1+q(n,n-1);

    正整数n的最大加数不大于n的划分由最大加数=n的划分和最大加数≤n-1的划分组成。

  4. q(n,m)=q(n,m−1)+q(n−m,m),n>m>1;q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;

    正整数n的最大加数不大于m的划分由最大加数≤m-1的划分和最大加数=m的划分组成。

理解一下：

  • 最大加数=m的划分： 相当于给定了一个前提条件，即至少有一个划分成m，故先减去这个被划分走了的m，则剩下的可以再划分的大小为 “n-m”，故最终的表达式为q(n-m,m)。

  • 最大加数≤m-1的划分： 上一步已经求出了最大划分为m的情况的划分数，所以接下来就只需求出 最大划分为m-1 这一情况的划分数，那么我们只需要约束最大划分数为m-1，进而得到最终的表达式为q(n,m-1)。

注：在理解了递归关系4之后，我们再反过来分析关系3：
3.其实是4.的特殊情况，即m=n，那么

q(n,n)=q(n,n−1)+q(n−n,n)−−式①q(n,n) = q(n, n-1) + q(n-n, n) -- 式①

=q(n,n−1)+q(0,n)−−式②= q(n, n-1) + q(0, n) -- 式②

  • 在这里我们单单从表达式上理解的话，q(0, n) 在题目中是没有意义的，因为这是一个 “正整数” 的划分问题，n=0相当于没有东西可以划分了。
  • 但是从实际意义上出发进行理解，q(n-n,n)就是最大加数=n的划分，即n大的正整数需要划分成包含一个大小为n的划分组合，那不就是只有“ n=n ”这一个划分嘛。

综上，可以知道：q(n-n, n) = 1，从而得到前面的关系3：q(n, n-1) + q(n-n, n) = q(n, n-1) + 1，而写成式②这样反而会导致表达式失去意义。

递推公式的直观理解 🤔
通过一个例子来理解:
假设n=5，m=3时：
q(5,3)可以分为两类：不使用 3 作为加数：q(5,2)
使用至少一个 3：q(5-3,3) = q(2,2)

最终的递推公式：

q(n,m)={1, n≥1,m=1q(n,n), n<m1+q(n,n−1), n=mq(n,m−1)+q(n−m,m), n>m>1q(n,m)=\begin{cases} 1 & \text{, } n \geq 1,m=1 \\ q(n,n) & \text{, } n < m & \\ 1 + q(n,n-1) & \text{, } n = m \\ q(n,m-1)+q(n-m,m) & \text{, } n>m>1 \end{cases}

求正整数n的不同划分个数，即求正整数n的划分数p(n)=q(n,n)。

根据分析结果写动态规划求解的递推公式

我们使用二维数组dp[i][j]dp[i][j]，记录划分整数i且最大划分不超过j的最大划分个数，则递推公式为：

dp[i][j]={1, i≥1,j=1dp[i][i], i<j1+dp[i−j][j], i=jdp[i][j−1]+dp[i−j][j], i>j>1dp[i][j]=\begin{cases} 1 & \text{, } i \geq 1,j=1 \\ dp[i][i] & \text{, } i < j & \\ 1 + dp[i-j][j] & \text{, } i = j \\ dp[i][j-1]+dp[i-j][j] & \text{, } i>j>1 \end{cases}

4. 以自底向上方式计算最优值💻

基于递推关系式，用二维数组存储dp[i][j]dp[i][j]的结果，通过填记录最优值的表求解。以下为实现步骤：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>

#define MAX_N 100 // 设置最大 n 的范围

// 动态规划函数：计算整数划分
int integerPartition(int n)
{
  int dp[MAX_N + 1][MAX_N + 1] = {0}; // 初始化动态规划数组

  // 初始化边界条件
  for (int i = 0; i <= n; i++)
  {
    dp[i][1] = 1; // 最大加数m为 1 时，只有一种划分方式
  }

  for (int i = 1; i <= n; i++)
  {
    for (int j = 2; j <= n; j++)
    {
      if (i < j)
      {
        dp[i][j] = dp[i][i]; // n < m 的情况
      }
      else if (i == j)
      {
        dp[i][j] = 1 + dp[i][i - 1]; // n == m 的情况
      }
      else
      {
        dp[i][j] = dp[i][j - 1] + dp[i - j][j]; //  n>m>1的情况，转移方程
      }
    }
  }

  return dp[n][n]; // 返回最终结果
}

int main()
{
  int n;
  printf("请输入正整数 n：");
  scanf("%d", &n);

  int res = integerPartition(n);

  printf("正整数 %d 的划分数是：%d\n", n, res);
  return 0;
}

运行结果：
用例运行结果

5. 优化 📊

问题回顾

我们需要计算将正整数 nn 划分为一系列正整数之和的划分数。例如，n=4n = 4 的划分数为 5，划分方式为：

1
2
3
4
5
4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

原始二维动态规划

在原始代码中，我们使用了一个二维数组 dp[i][j]，其中：

  • dp[i][j] 表示将整数 ii 划分为最大加数不超过 jj 的划分数。

递推公式为：

  1. 如果 i<ji < j，则 dp[i][j] = dp[i][i]。

  2. 如果 i=ji = j，则 dp[i][j] = 1 + dp[i][j - 1]。

  3. 如果 i>ji > j，则 dp[i][j] = dp[i][j - 1] + dp[i - j][j]。

这个递推公式的核心思想是：

  • 将划分分为两类：不包含 jj 的划分 和 包含 jj 的划分

    • 不包含 jj 的划分数是 dp[i][j - 1]。
    • 包含 jj 的划分数是 dp[i - j][j]。

优化为一维动态规划

我们观察到，二维数组 dp[i][j] 的更新只依赖于当前行和上一行的值。具体来说：

  • 在计算 dp[i][j] 时，只需要 dp[i][j - 1] 和 dp[i - j][j]。

  • 这意味着我们可以用一维数组 dp[i] 来存储当前行的值，并通过滚动更新的方式计算。

实际上，二维动态规划的依赖关系是：
dp[i][j] 依赖于：

  1. dp[i][j−1]（当前行的前一个值）。

  2. dp[i−j][j]（上一行的某个值）。

这种依赖关系并不是简单的“当前行和上一行”，而是涉及到了更复杂的跳跃依赖（因为 dp[i−j][j] 的位置与 dp[i][j] 的位置相差 j 行）。

为什么可以优化为一维数组？
尽管依赖关系复杂，但我们仍然可以优化为一维数组，原因如下：

  1. 滚动更新的思想：

在计算 dp[i][j] 时，我们只需要 dp[i][j−1] 和 dp[i−j][j]。

如果我们按照一定的顺序更新 dp[i]，可以确保在计算 dp[i] 时，dp[i−j] 已经被正确更新。

  1. 枚举顺序的调整：

在优化后的代码中，我们首先枚举最大加数 j（从 1 到 n），然后枚举目标数 i（从 j 到 n）。

这种枚举顺序确保了在计算 dp[i] 时，dp[i−j] 已经被正确更新。

  1. 一维数组的含义：

优化后的一维数组 dp[i] 表示将整数 i 划分为一系列正整数之和的划分数。

在枚举 j 时，我们逐步更新 dp[i]，使其包含所有可能的划分。

优化后的递推公式

优化后的递推公式为：

dp[i]=dp[i]+dp[i−j]dp[i] = dp[i] + dp[i - j]

其中：

  • dp[i] 表示将整数 ii 划分为一系列正整数之和的划分数。

  • j 是当前枚举的最大加数。

递推公式的推导

  1. 初始化：

    • dp[0] = 1，表示空划分（即不选任何数）。

  2. 枚举最大加数 jj：

    • 对于每个 jj（从 1 到 nn），我们更新 dp[i] 的值。
    • 更新规则：dp[i] += dp[i - j]。

  3. 解释更新规则：

    • dp[i] 表示将 ii划分为一系列正整数之和的划分数。
    • dp[i - j] 表示将 i−ji - j 划分为一系列正整数之和的划分数。
    • 当我们加上 dp[i - j] 时，实际上是在考虑所有包含 jj 的划分。
    • 例如，如果 j=2j = 2，那么 dp[i] += dp[i - 2] 表示将 ii 划分为包含 2 的划分数。

  4. 为什么可以这样更新：

    • 在原始二维动态规划中，dp[i][j] = dp[i][j - 1] + dp[i - j][j]。
    • 优化后的一维动态规划中，dp[i] 相当于 dp[i][j]，而 dp[i - j] 相当于 dp[i - j][j]。
    • 通过滚动更新，dp[i] 的值会逐步累积，最终得到正确的结果。

示例演示

以 n=4n = 4 为例，演示优化后的动态规划过程：

  1. 初始化：

    • dp = [1, 0, 0, 0, 0]，其中 dp[0] = 1。

  2. 枚举 j=1j = 1：

    • 更新 dp[i] 的值：
      • dp[1] += dp[0] → dp[1] = 1
      • dp[2] += dp[1] → dp[2] = 1
      • dp[3] += dp[2] → dp[3] = 1
      • dp[4] += dp[3] → dp[4] = 1
    • 此时 dp = [1, 1, 1, 1, 1]。

  3. 枚举 j=2j = 2：

    • 更新 dp[i] 的值：
      • dp[2] += dp[0] → dp[2] = 1 + 1 = 2
      • dp[3] += dp[1] → dp[3] = 1 + 1 = 2
      • dp[4] += dp[2] → dp[4] = 1 + 2 = 3
    • 此时 dp = [1, 1, 2, 2, 3]。

  4. 枚举 j=3j = 3：

    • 更新 dp[i] 的值：
      • dp[3] += dp[0] → dp[3] = 2 + 1 = 3
      • dp[4] += dp[1] → dp[4] = 3 + 1 = 4
    • 此时 dp = [1, 1, 2, 3, 4]。

  5. 枚举 j=4j = 4：

    • 更新 dp[i] 的值：
      • dp[4] += dp[0] → dp[4] = 4 + 1 = 5
    • 此时 dp = [1, 1, 2, 3, 5]。

最终，dp[4] = 5，即 n=4n = 4 的划分数为 5。

实现优化后的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>

#define MAX_N 100 // 设置最大 n 的范围

// 动态规划函数：计算整数划分
int integerPartition(int n)
{
  int dp[MAX_N + 1] = {0}; // 初始化一维动态规划数组
  dp[0] = 1; // 初始化 dp[0] = 1，表示空划分

  for (int j = 1; j <= n; j++) // 枚举最大加数 j
  {
    for (int i = j; i <= n; i++) // 枚举目标数 i
    {
      dp[i] += dp[i - j]; // 转移方程：dp[i] = dp[i] + dp[i - j]
    }
  }

  return dp[n]; // 返回最终结果
}

int main()
{
  int n;
  printf("请输入正整数 n：");
  scanf("%d", &n);

  int res = integerPartition(n);

  printf("正整数 %d 的划分数是：%d\n", n, res);
  return 0;
}

优化总结

通过分析原始二维动态规划的递推公式，我们发现：

  • 只需要一维数组即可存储中间结果。

  • 通过枚举最大加数 jj 并更新 dp[i]，可以逐步计算出划分数。

优化后的递推公式为：

dp[i]=dp[i]+dp[i−j]dp[i] = dp[i] + dp[i - j]

这种方法不仅减少了空间复杂度，还保持了相同的时间复杂度 O(n2)O(n^2)。

6. 扩展思考 🎯

6.1 相关问题

  1. 完全背包问题

  2. 硬币找零问题

  3. 数字组合问题

6.2 实际应用场景

  1. 财务系统中的支付方案设计

  2. 资源分配问题

  3. 任务调度优化

总结 🎉

整数划分问题是一个非常经典的动态规划问题，不仅需要掌握问题的解决方法，更重要的是理解了动态规划的思维方式和优化技巧：整数划分问题通过动态规划实现，将问题分解为子问题求解，尝试将空间复杂度优化。

通过学习和实现这个问题，能够深入理解动态规划的核心思想，掌握处理类似问题的技巧。✨

🤔 思考题

  1. 如何修改代码来输出所有的划分方案？

  2. 如果限制划分中数字不能重复使用，应该如何修改算法？

  3. 如果要求划分中的数字必须是奇数，如何调整递推公式？

技术 算法
#算法 #动态规划
算法学习—整数划分
https://huazzi.me/posts/131912631/
作者
Huazzi
发布于
2025年1月21日
许可协议