线性动态规划：丑数 II

字数 2889 2025-10-28 20:05:13

线性动态规划：丑数 II

题目描述
给你一个整数 n，请你找出并返回第 n 个丑数。
丑数是指只包含质因数 2、3 和/或 5 的正整数。例如，1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

解题过程

理解问题与定义状态
我们需要生成一个丑数序列，其中每个数都是由前面的丑数乘以 2、3 或 5 得到的（1 是第一个丑数）。关键在于如何按顺序生成它们，避免遗漏或重复。
我们可以使用动态规划，定义一个数组 dp，其中 dp[i] 表示第 i 个丑数（i 从 1 开始计数）。因此，我们的目标就是计算 dp[n]。
初始状态：dp[1] = 1，因为 1 是第一个丑数。
关键思路：三指针法
单纯地逐个判断每个数是否是丑数效率很低。一个高效的方法是使用三个指针（或索引）p2, p3, p5。
- p2 指向下一个将要乘以 2 的丑数。
- p3 指向下一个将要乘以 3 的丑数。
- p5 指向下一个将要乘以 5 的丑数。
  在每一步中，我们计算：
  num2 = dp[p2] * 2
  num3 = dp[p3] * 3
  num5 = dp[p5] * 5
  然后，下一个丑数就是这三个数中的最小值。这样我们就能保证丑数序列是严格递增的。
状态转移方程
设当前要计算 dp[i]。
1. 计算候选值：
  candidate2 = dp[p2] * 2
  candidate3 = dp[p3] * 3
  candidate5 = dp[p5] * 5
2. dp[i] = min(candidate2, candidate3, candidate5)
3. 更新指针：如果 dp[i] 等于某个候选值，那么对应的指针就向后移动一位（p2++, p3++ 或 p5++）。注意：如果 dp[i] 同时等于多个候选值（例如 6 = 23 = 32），那么这些对应的指针都需要移动，以避免在后续序列中产生重复的丑数。
逐步计算示例（以 n=10 为例）
初始化：dp[1] = 1, p2 = 1, p3 = 1, p5 = 1
- i=2:
  num2 = dp[1]*2 = 2
  num3 = dp[1]*3 = 3
  num5 = dp[1]*5 = 5
  min(2,3,5) = 2 -> dp[2] = 2
  因为 2 来自 num2，所以 p2 移动到 2 (p2++)。p3 和 p5 不变。
  序列: [1, 2]
- i=3:
  num2 = dp[2]*2 = 4
  num3 = dp[1]*3 = 3
  num5 = dp[1]*5 = 5
  min(4,3,5) = 3 -> dp[3] = 3
  因为 3 来自 num3，所以 p3 移动到 2 (p3++)。p2 和 p5 不变。
  序列: [1, 2, 3]
- i=4:
  num2 = dp[2]*2 = 4
  num3 = dp[2]*3 = 6
  num5 = dp[1]*5 = 5
  min(4,6,5) = 4 -> dp[4] = 4
  因为 4 来自 num2，所以 p2 移动到 3 (p2++)。p3 和 p5 不变。
  序列: [1, 2, 3, 4]
- i=5:
  num2 = dp[3]*2 = 6
  num3 = dp[2]*3 = 6
  num5 = dp[1]*5 = 5
  min(6,6,5) = 5 -> dp[5] = 5
  因为 5 来自 num5，所以 p5 移动到 2 (p5++)。p2 和 p3 不变。
  序列: [1, 2, 3, 4, 5]
- i=6:
  num2 = dp[3]*2 = 6
  num3 = dp[2]*3 = 6
  num5 = dp[2]*5 = 10
  min(6,6,10) = 6
  注意，6 同时等于 num2 和 num3。
  -> dp[6] = 6
  因为 6 来自 num2 和 num3，所以 p2 移动到 4 (p2++)，p3 移动到 3 (p3++)。p5 不变。
  序列: [1, 2, 3, 4, 5, 6]
- i=7:
  num2 = dp[4]*2 = 8
  num3 = dp[3]*3 = 9
  num5 = dp[2]*5 = 10
  min(8,9,10) = 8 -> dp[7] = 8
  p2 移动到 5 (p2++)
  序列: [1, 2, 3, 4, 5, 6, 8]
- i=8:
  num2 = dp[5]*2 = 10
  num3 = dp[3]*3 = 9
  num5 = dp[2]*5 = 10
  min(10,9,10) = 9 -> dp[8] = 9
  p3 移动到 4 (p3++)
  序列: [1, 2, 3, 4, 5, 6, 8, 9]
- i=9:
  num2 = dp[5]*2 = 10
  num3 = dp[4]*3 = 12
  num5 = dp[2]*5 = 10
  min(10,12,10) = 10
  注意，10 同时等于 num2 和 num5。
  -> dp[9] = 10
  p2 移动到 6 (p2++), p5 移动到 3 (p5++)
  序列: [1, 2, 3, 4, 5, 6, 8, 9, 10]
- i=10:
  num2 = dp[6]*2 = 12
  num3 = dp[4]*3 = 12
  num5 = dp[3]*5 = 15
  min(12,12,15) = 12 -> dp[10] = 12
  p2 移动到 7 (p2++), p3 移动到 5 (p3++)
  序列: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12]
因此，第 10 个丑数是 12。
算法总结
1. 初始化动态规划数组 dp，大小为 n+1，dp[1] = 1。
2. 初始化三个指针 p2 = 1, p3 = 1, p5 = 1。
3. 从 i = 2 循环到 i = n：
  a. 计算 num2 = dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5。
  b. dp[i] = min(num2, num3, num5)。
  c. 如果 dp[i] == num2，则 p2++。
  如果 dp[i] == num3，则 p3++。
  如果 dp[i] == num5，则 p5++。
4. 返回 dp[n]。

这个方法的时间复杂度是 O(n)，空间复杂度也是 O(n)，用于存储丑数序列。它高效地按顺序生成了所有丑数，避免了重复计算和排序。

线性动态规划：丑数 II 题目描述给你一个整数 n，请你找出并返回第 n 个丑数。丑数是指只包含质因数 2、3 和/或 5 的正整数。例如，1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。解题过程理解问题与定义状态我们需要生成一个丑数序列，其中每个数都是由前面的丑数乘以 2、3 或 5 得到的（1 是第一个丑数）。关键在于如何按顺序生成它们，避免遗漏或重复。我们可以使用动态规划，定义一个数组 dp ，其中 dp[i] 表示第 i 个丑数（i 从 1 开始计数）。因此，我们的目标就是计算 dp[n] 。初始状态： dp[1] = 1 ，因为 1 是第一个丑数。关键思路：三指针法单纯地逐个判断每个数是否是丑数效率很低。一个高效的方法是使用三个指针（或索引） p2 , p3 , p5 。 p2 指向下一个将要乘以 2 的丑数。 p3 指向下一个将要乘以 3 的丑数。 p5 指向下一个将要乘以 5 的丑数。在每一步中，我们计算： num2 = dp[p2] * 2 num3 = dp[p3] * 3 num5 = dp[p5] * 5 然后，下一个丑数就是这三个数中的最小值。这样我们就能保证丑数序列是严格递增的。状态转移方程设当前要计算 dp[i] 。计算候选值： candidate2 = dp[p2] * 2 candidate3 = dp[p3] * 3 candidate5 = dp[p5] * 5 dp[i] = min(candidate2, candidate3, candidate5) 更新指针：如果 dp[i] 等于某个候选值，那么对应的指针就向后移动一位（ p2++ , p3++ 或 p5++ ）。注意：如果 dp[i] 同时等于多个候选值（例如 6 = 2 3 = 3 2），那么这些对应的指针都需要移动，以避免在后续序列中产生重复的丑数。逐步计算示例（以 n=10 为例）初始化： dp[1] = 1 , p2 = 1 , p3 = 1 , p5 = 1 i=2: num2 = dp[1]*2 = 2 num3 = dp[1]*3 = 3 num5 = dp[1]*5 = 5 min(2,3,5) = 2 -> dp[2] = 2 因为 2 来自 num2 ，所以 p2 移动到 2 ( p2++ )。 p3 和 p5 不变。序列: [ 1, 2 ] i=3: num2 = dp[2]*2 = 4 num3 = dp[1]*3 = 3 num5 = dp[1]*5 = 5 min(4,3,5) = 3 -> dp[3] = 3 因为 3 来自 num3 ，所以 p3 移动到 2 ( p3++ )。 p2 和 p5 不变。序列: [ 1, 2, 3 ] i=4: num2 = dp[2]*2 = 4 num3 = dp[2]*3 = 6 num5 = dp[1]*5 = 5 min(4,6,5) = 4 -> dp[4] = 4 因为 4 来自 num2 ，所以 p2 移动到 3 ( p2++ )。 p3 和 p5 不变。序列: [ 1, 2, 3, 4 ] i=5: num2 = dp[3]*2 = 6 num3 = dp[2]*3 = 6 num5 = dp[1]*5 = 5 min(6,6,5) = 5 -> dp[5] = 5 因为 5 来自 num5 ，所以 p5 移动到 2 ( p5++ )。 p2 和 p3 不变。序列: [ 1, 2, 3, 4, 5 ] i=6: num2 = dp[3]*2 = 6 num3 = dp[2]*3 = 6 num5 = dp[2]*5 = 10 min(6,6,10) = 6 注意，6 同时等于 num2 和 num3 。 -> dp[6] = 6 因为 6 来自 num2 和 num3 ，所以 p2 移动到 4 ( p2++ )， p3 移动到 3 ( p3++ )。 p5 不变。序列: [ 1, 2, 3, 4, 5, 6 ] i=7: num2 = dp[4]*2 = 8 num3 = dp[3]*3 = 9 num5 = dp[2]*5 = 10 min(8,9,10) = 8 -> dp[7] = 8 p2 移动到 5 ( p2++ ) 序列: [ 1, 2, 3, 4, 5, 6, 8 ] i=8: num2 = dp[5]*2 = 10 num3 = dp[3]*3 = 9 num5 = dp[2]*5 = 10 min(10,9,10) = 9 -> dp[8] = 9 p3 移动到 4 ( p3++ ) 序列: [ 1, 2, 3, 4, 5, 6, 8, 9 ] i=9: num2 = dp[5]*2 = 10 num3 = dp[4]*3 = 12 num5 = dp[2]*5 = 10 min(10,12,10) = 10 注意，10 同时等于 num2 和 num5 。 -> dp[9] = 10 p2 移动到 6 ( p2++ ), p5 移动到 3 ( p5++ ) 序列: [ 1, 2, 3, 4, 5, 6, 8, 9, 10 ] i=10: num2 = dp[6]*2 = 12 num3 = dp[4]*3 = 12 num5 = dp[3]*5 = 15 min(12,12,15) = 12 -> dp[10] = 12 p2 移动到 7 ( p2++ ), p3 移动到 5 ( p3++ ) 序列: [ 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 ] 因此，第 10 个丑数是 12。算法总结初始化动态规划数组 dp ，大小为 n+1， dp[1] = 1 。初始化三个指针 p2 = 1 , p3 = 1 , p5 = 1 。从 i = 2 循环到 i = n ： a. 计算 num2 = dp[p2] * 2 , num3 = dp[p3] * 3 , num5 = dp[p5] * 5 。 b. dp[i] = min(num2, num3, num5) 。 c. 如果 dp[i] == num2 ，则 p2++ 。如果 dp[i] == num3 ，则 p3++ 。如果 dp[i] == num5 ，则 p5++ 。返回 dp[n] 。这个方法的时间复杂度是 O(n)，空间复杂度也是 O(n)，用于存储丑数序列。它高效地按顺序生成了所有丑数，避免了重复计算和排序。