劍指Offer經典題解：動態規劃求第N個醜數（九度OJ 1214）

題目描述

把只包含質因子 2、3、5 的數稱為醜數。習慣上 1 是第一個醜數。求按從小到大順序的第 N 個醜數（1 ≤ N ≤ 1500）。

算法演進：從暴力到優雅

❌ 方法一：暴力檢測（超時）

逐個自然數檢測是否為醜數，反覆除以 2、3、5 直到不能整除，最後判斷是否為 1。時間複雜度極高，N=1500 時嚴重超時。

✅ 方法二：動態規劃 + 三指針（AC）

核心洞察：每個醜數都是前面某個醜數乘以 2、3 或 5 得到的。維護三個指針 p2、p3、p5，分別指向「乘以 2/3/5 後大於當前最大醜數」的最小位置。

算法流程

1. 初始化：ugly[0] = 1，三指針均指向索引 0
2. 每輪計算三候選值：next2 = ugly[p2]*2、next3 = ugly[p3]*3、next5 = ugly[p5]*5
3. 取最小值作為下一個醜數：next = min(next2, next3, next5)
4. 將產生最小值的指針後移（可能多個同時後移，去重）
5. 重複直到生成 1500 個醜數

關鍵代碼

void generateUglyNumbers() {
    ugly[0] = 1;
    int p2 = 0, p3 = 0, p5 = 0;

    for (int i = 1; i < 1500; ++i) {
        int next2 = ugly[p2] * 2;
        int next3 = ugly[p3] * 3;
        int next5 = ugly[p5] * 5;

        ugly[i] = min(next2, min(next3, next5));

        if (ugly[i] == next2) ++p2;
        if (ugly[i] == next3) ++p3;
        if (ugly[i] == next5) ++p5;
    }
}

圖解演示（前10個醜數生成）

複雜度分析

• 時間：O(N) —— 每個醜數只計算一次，三指針單調遞增
• 空間：O(N) —— 存儲 1500 個整數

工程落地建議

1. 預計算離線化：主程序啟動時一次性生成查表數組，查詢時 O(1) 直接返回
2. 類型選擇：第 1500 個醜數為 859963392，int 足夠（< 2³¹）
3. 多測試用例：使用 while(scanf("%d", &n) != EOF) 循環讀取

總結

醜數問題是動態規劃與多指針技巧的經典結合。關鍵在於識別「有序序列由歷史元素乘因子生成」的遞推結構，並用三指針高效去重合併。這種「多路歸併」思想廣泛應用於堆、優先隊列等場景。