第 n 个丑数：从暴力枚举到动态规划 + 多指针

四、动态规划 + 多指针：精准生成与去重

为了只生成丑数、按序生成、不重复生成，可以采用动态规划配合多指针的方案。
这套方案的本质是：用空间记录状态，用指针控制迭代，用取最小保证有序，用多分支判断完成去重。

1. 状态设计

定义数组 dp：

• dp[i] 表示第 i+1 个丑数；
• 初始化 dp[0] = 1，对应第一个丑数。

2. 指针的意义

既然每个新丑数只能来自：

• 某个旧丑数 ×2
• 某个旧丑数 ×3
• 某个旧丑数 ×5

我们用三个指针分别标记当前应该参与乘法的位置：

• p2：下一个要 ×2 的丑数下标
• p3：下一个要 ×3 的丑数下标
• p5：下一个要 ×5 的丑数下标

初始时都指向 0，即从第一个丑数开始。

3. 递推规则

对每一个新位置 dp[i]：

1. 计算三个候选值：
   • num2 = dp[p2] * 2
   • num3 = dp[p3] * 3
   • num5 = dp[p5] * 5
2. 取三者最小值作为当前丑数，保证严格递增；
3. 如果当前丑数等于某个候选值，就将对应指针后移一位：
   • 若等于 num2，p2++
   • 若等于 num3，p3++
   • 若等于 num5，p5++

这里必须使用独立的 if 而非 else if，目的是：
当多个候选值相等时（如 6 同时由 ×2 和 ×3 得到），多个指针同时后移，从根源上去重，避免后续重复生成同一数字。

五、实现代码（C++）

class Solution {
public:
    int nthUglyNumber(int n) {
        if (n == 1) return 1;
        vector<int> dp(n);
        dp[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0;
        for (int i = 1; i < n; ++i) {
            int num2 = dp[p2] * 2;
            int num3 = dp[p3] * 3;
            int num5 = dp[p5] * 5;
            dp[i] = min(min(num2, num3), num5);
            if (dp[i] == num2) p2++;
            if (dp[i] == num3) p3++;
            if (dp[i] == num5) p5++;
        }
        return dp[n - 1];
    }
};

六、复杂度与可扩展性思考

时间复杂度

• 只进行一轮从 1 到 n-1 的遍历；
• 每一步仅包含固定次数的乘法、比较、指针移动；
• 时间复杂度为 O(n)，是该问题理论下界。

空间复杂度

• 使用长度为 n 的 dp 数组保存历史丑数；
• 空间复杂度 O(n)。

在工程视角下：

• 如果 n 上限已知且不大，这种空间换时间的方式非常划算；
• 若追求极致空间，可以只保留最近几个关键值，但会明显降低可读性与可维护性，除非资源极度受限，否则不建议。

可扩展启发

这套思路不局限于丑数：

• 只要目标序列满足：由基础因子从已有元素生成；
• 且需要有序、不重复；
  都可以使用：
  动态规划记录状态 + 多指针控制迭代位置 + 取最小保证有序。

例如：

• 超级丑数（质因数不限于 2、3、5）
• 某些带限制的倍数序列生成
• 流式生成有序目标集合

都可以在这套框架上扩展，只需要调整指针数量与候选生成规则。

七、小结

第 n 个丑数从暴力到最优解的过程，本质是三次思维升级：

1. 从**'筛选所有数'升级为'只生成目标数'**；
2. 从**'无序生成'升级为'按序生成'**；
3. 从**'可能重复'升级为'精准去重'**。

动态规划 + 多指针并没有复杂数学推导，而是用最朴素的方式，把每一步多余计算都砍掉，只保留必要的状态与转移。这种思路在算法训练中是基础，在实际工程中同样适用——很多高性能逻辑，并不是靠花哨技巧，而是靠精准定义状态、严格控制迭代、彻底消除无效计算来实现的。

手动模拟前 10 个丑数的生成过程，观察指针移动与去重逻辑，能更稳定地掌握这一类生成型问题的通用解法。