★ FEATURED ARTICLE 丑数1和2是动态规划里一对特别适合放在一起练的题。别被名字误导丑数和“长得丑”没关系算法里它是正经数学名词只包含质因数2、3、5的正整数并且大家约定1也算丑数。题目通常有两个版本第一个版本让你判断一个数是不是丑数第二个版本让你求第n个丑数具体是多少。前者简单到很多人觉得“就这”后者却常常让人卡住原因很微妙——从“判断一个数”切换到“按顺序生成一串数”思维方式完全不同。两个版本连着做恰好能把动态规划里一个很经典的多指针生成有序序列的套路彻底吃透这也是我为什么说它是一道不错的题。这篇内容适合三类人看刚开始学动态规划、想找一道不太难的题来敲门的人准备面试、想把“丑数2”讲清楚的人以及已经刷过题但只记住了代码、没真正理解三指针为什么成立的人。我会从丑数1开始一路拆到丑数2的动态规划解法把状态转移、去重、边界这些问题全部摊开讲。1. 丑数1先解决“判断一个数”的问题1.1 题目到底在问什么丑数1的题干很短给定一个整数判断它是否为丑数。丑数的定义是“只包含质因数2、3、5的正整数”。这句话拆开看意思是这个数必须能整除2或者能整除3或者能整除5而且不断除下去最后只剩下1。举个例子6等于2乘3两个因子都是2、3、5集合里的所以是丑数。8等于2的三次方也是丑数。14等于2乘7虽然能整除2但剩下一个77不是2、3、5中的任何一个所以14不是丑数。这个例子很重要很多人判断的时候只看“能否被2/3/5整除”结果把14这种数放过去了。还有两个约定俗成的细节1是丑数因为1没有任何质因数空集也算“只包含”2、3、5小于等于0的整数不是丑数因为丑数定义在正整数范围内而且负数和0的质因数分解没有意义。1.2 暴力判断法的实现判断逻辑其实非常直接把这个数能被2整除的部分全除掉能被3整除的部分全除掉能被5整除的部分全除掉最后看看剩下的是不是1。这里可以用一个循环依次处理2、3、5三个因子。def is_ugly(n): if n 0: return False for factor in (2, 3, 5): while n % factor 0: n // factor return n 1这个代码有几点值得讲。第一负数和0要先排除否则后面取余运算会出问题而且定义上也不允许。第二三个因子处理的顺序不影响结果因为乘法交换律决定了“先除2再除3”和“先除3再除2”最终都会清掉所有对应因子。第三while循环要把当前因子除干净比如输入是16那么2要连续除4次。我见过有人写成“if n % 2 0: n // 2”只除一次这样判断16这种数就会出错。虽然可以用递归或者反过来用2、3、5的幂次去匹配但最稳妥的还是这种“除到不能除为止”的写法。2. 丑数2从判断到生成难度瞬间上来了2.1 如果逐个判断会发生什么丑数2的问题变成给定正整数n求第n个丑数。什么叫第n个就是从小到大排列丑数序列1、2、3、4、5、6、8、9、10、12……其中第1个是1第2个是2第3个是3依次类推。最先想到的办法当然是暴力从1开始逐个调用is_ugly判断是丑数就计数直到数到第n个。这个做法在n很小的时候没问题但n一旦变大性能就开始失控。原因有两个。第一个原因丑数在自然数里越往后越稀疏。1到10之间有一半是丑数但100以后大部分整数都带有7、11、13这样的质因子丑数出现的密度迅速下降。第二个原因判断一个数的耗时和数字本身的大小相关对于大数要不断做除法和取余计算量不可忽视。实测下来用暴力判断去找第500个丑数还能勉强在可接受时间内跑完但去找第1000个丑数时已经能明显感觉到卡顿如果题目把n的范围放到1690甚至更大暴力方案基本没戏。所以丑数2的核心难点不是“判断一个数是不是丑数”而是“怎么按顺序生成丑数跳过所有非丑数”。2.2 动态规划的突破口生成而不是判断这时候得换一个思路每一个大于1的丑数能不能由更小的丑数算出来当然可以。丑数的定义是“质因数只有2、3、5”所以任何一个丑数都可以分解成“某个更小的丑数乘以2”或者“乘以3”或者“乘以5”的形式。反过来想如果我已经有了一个按从小到大排好的丑数序列那么把序列里的每一个数分别乘以2、3、5得到的所有结果一定还是丑数因为这些结果只会在原来的质因数集合上多加一个2、3或5不会引入新的质因子。但这里立刻出现三个问题一是乘法结果会重复比如2乘3等于63乘2也等于6二是乘法结果不是天然有序的2乘5等于105乘2也等于10但10比2乘6等于12要小三是如果直接把所有“已有丑数乘因子”的结果都算出来数量会爆炸根本没法维护。动态规划的思路就是把这三个问题一起解决一次只取当前最小的那个乘积作为下一个丑数同时用三个指针分别记录“乘2、乘3、乘5”各自进行到了序列里的哪个位置。这种做法本质上是一种“多路归并”每次从三路候选中挑最小值然后推进对应的指针。3. 三指针动态规划状态定义与核心推导3.1 状态定义定义dp[i]表示第i个丑数dp是一个长度为n1的数组下标从1开始用dp[1] 1。再定义三个指针p2、p3、p5初始都指向1。这三个指针的含义要理解准确p2表示“下一个和2相乘的丑数是dp[p2]”p3表示“下一个和3相乘的丑数是dp[p3]”p5表示“下一个和5相乘的丑数是dp[p5]”。为什么需要三个指针而不是一个因为同一个丑数乘以2、3、5会得到三个不同的候选这三个候选可能相差很远。比如当前指针都指到第2个丑数2那么候选是4、6、10但如果p2推进得快p3推进得慢那么后续候选可能是8、6、15。三个指针各自独立推进才能保证每次比较的都是“当前各自能给出的最小值”。3.2 状态转移方程第i个丑数的候选来源有三个a dp[p2] * 2b dp[p3] * 3c dp[p5] * 5取最小值就是第i个丑数dp[i] min(a, b, c)然后把所有等于这个最小值的候选对应的指针都向右移动一格。这里必须用三个独立的if判断而不是if-elif结构因为a、b、c可能有两个甚至三个完全相等如果只用一个elif相等的候选就不会被跳过下次会被重复计算。3.3 用例子手推一遍手动模拟前几个丑数的生成过程能直观看到指针是怎么移动的。初始状态dp[1] 1p2 1p3 1p5 1。计算dp[2]a dp[1] * 2 2b dp[1] * 3 3c dp[1] * 5 5。最小是2所以dp[2] 2p2从1变成2。计算dp[3]a dp[2] * 2 4b dp[1] * 3 3c dp[1] * 5 5。最小是3所以dp[3] 3p3从1变成2。计算dp[4]a dp[2] * 2 4b dp[2] * 3 6c dp[1] * 5 5。最小是4所以dp[4] 4p2从2变成3。计算dp[5]a dp[3] * 2 6b dp[2] * 3 6c dp[1] * 5 5。最小是5所以dp[5] 5p5从1变成2。计算dp[6]a dp[3] * 2 6b dp[2] * 3 6c dp[2] * 5 10。最小是6且a和b都等于6所以dp[6] 6p2和p3同时加1p2变成4p3变成3p5保持2。这一步很重要如果只推进一个指针dp[3] * 2 6或者dp[2] * 3 6还会在下一轮继续出现产生重复的6。把这个过程列成表格会更清楚i候选a候选b候选cdp[i]更新操作22352p234353p344654p256655p5666106p2, p3通过手推能看出一个关键规律每一轮取到的最小值必然是当前所有可能乘积中最小的那个因为三个指针各自指向的dp元素都保持递增而乘法因子2、3、5是固定常数所以三路乘积都是单调递增的。把它们合并后取最小就能保证生成序列的全局有序性。这有点像多路归并排序里每次取最小的那个头元素。4. 完整代码实现与细节说明4.1 代码与注释用Python写出来非常简洁。def nth_ugly_number(n): if n 1: return 1 dp [0] * (n 1) dp[1] 1 p2 p3 p5 1 for i in range(2, n 1): a dp[p2] * 2 b dp[p3] * 3 c dp[p5] * 5 cur min(a, b, c) dp[i] cur if cur a: p2 1 if cur b: p3 1 if cur c: p5 1 return dp[n]这段代码的边界情况需要注意n等于1时直接返回dp[1]也就是1不需要走循环dp数组大小是n1下标从1开始所以初始化时用“0”填充也不会影响结果因为真正赋值的区间是2到n。4.2 三个if而不是elif很多人第一次写这个题会把三个指针更新写成if-elif的形式if cur a: p2 1 elif cur b: p3 1 elif cur c: p5 1这个写法在大样例里会出错因为当两个候选值相同时比如6可以由2乘3和3乘2同时得到只更新一个指针会导致另一个“过期”的候选还在源头等着下一轮还会再生成一次6整个序列里出现重复元素。而丑数序列要求严格递增一旦出现重复后面的顺序全乱了。正确做法是三个独立的if让所有命中最小值的指针都同步前进。这个细节看起来不起眼却是整个方案能否正确工作的关键也是面试官喜欢追问的点一定要能说出来“为什么这样去重”。4.3 复杂度分析时间复杂度是O(n)因为只需要从2循环到n每次做三次乘法和一次最小值比较外加最多三次指针自增都是常数操作。空间复杂度是O(n)因为要保存长度为n1的dp数组。三个指针本身只是三个变量占用常数空间。如果只求第n个丑数理论上可以把前面的元素全丢掉只用三个位置滚动但那样做没有意义因为三个指针指向的dp元素下标是不确定的可能相差很远无法用常数个变量替代整个数组。所以这里的O(n)空间是必需的不能优化成O(1)。5. 常见问题与实战踩坑5.1 重复值问题前面已经提到6这个数字会被同时生成两次2乘3和3乘2。再往后看10也会被2乘5和5乘2同时生成15也会被3乘5和5乘3同时生成。如果不做去重序列就会变成1、2、3、4、5、6、6、8直接错误。去重的核心就是那三个独立的if判断。有一个小技巧可以自查在模拟第6个丑数时如果发现候选里面有两个6并且最后表里出现了两个连续的6说明指针更新改成了elif。用这个特征快速定位bug不用从头查数据。5.2 数组长度和边界问题dp数组要开n1个位置如果习惯从0开始存也可以把dp[0]浪费掉但循环写法要统一。我曾经见过有人dp只开n个位置下标却访问到dp[n]结果越界报错。还有一个容易忽略的边界是n0。题目一般不会让n0但如果你写代码的时候没做判断dp[1]就会越界。稳妥的做法是在函数开头加一句n 0直接返回0或者按题意抛出异常。不过实际刷题时n都是从1开始的这里更多是养成好习惯。5.3 如果质因数不止2、3、5怎么办这一类问题的通用形式叫“超级丑数”给一个质因数数组primes比如[2, 7, 13, 19]求第n个超级丑数。解法思路完全一样把三个指针扩展成和primes数组等长的指针数组每次计算primes里的每个质因数与对应指针指向的丑数的乘积取最小值再对所有命中最小值的指针加1。伪代码大概是def nth_super_ugly_number(n, primes): dp [0] * n dp[0] 1 pointers [0] * len(primes) for i in range(1, n): candidates [dp[pointers[j]] * primes[j] for j in range(len(primes))] dp[i] min(candidates) for j in range(len(primes)): if dp[i] candidates[j]: pointers[j] 1 return dp[n - 1]能看到这里说明你已经不是背代码而是理解了它的本质多路归并取最小相同值同步前进。这个模型非常通用很多看似不相关的题目比如合并K个有序链表、找出第K个最小的跨数组乘积底层都是这个思想。6. 我的一些实际做题经验和扩展思考6.1 做题顺序建议如果是第一次接触动态规划我建议按三步走。第一步先花十分钟把丑数1独立写出来确认自己对“丑数”的定义有直觉。第二步不要急着写代码拿纸笔手推第1到第10个丑数感受一下序列的增长规则。第三步再对照本文的三指针思路写丑数2写完以后故意把三个if改成elif看看输出哪里开始出错加深印象。我自己带人入门时发现直接上手写丑数2代码的人很容易被指针初始化、更新时机这些细节拦住而先手推过几个数的人反而一次就能写对。原因很简单手推过程中你已经发现了“6同时来自两个候选”这件事自然会在代码里用三个if去处理。6.2 面试和实际应用的延伸面试中这题能考察的东西不少。第一个是递推能力能不能把“丑数由丑数乘因子产生”这个性质转化成状态转移方程。第二个是边界意识负数和0的判断、n等于1时直接返回、重复候选的去重这些都是容易失分的小点。第三个是复杂度分析要能说出为什么O(n)比暴力判断快以及空间为什么不能优化成O(1)。还有一点值得留意这道题和斐波那契数列这类经典DP不一样它的状态不是“前一个状态简单相加”得到的而是“多个前序状态分别做乘法后取最小值”。这给初次接触的人一种陌生感但一旦适应动态规划里“状态由多个来源竞争产生”的模型就打开了。后面遇到戳气球、编辑距离这些更复杂的题目至少不会有“状态不知道怎么设计”的无力感。我个人的体会是把丑数1和2放在一起练习价值不在于记住某段代码而在于亲眼见证“判断一个数”和“生成一串数”之间的思维落差。那个落差里藏着的正是动态规划最朴素也最核心的东西用已经算过的结果构造出下一个结果而不是从头判断每个数。这道题的妙处在于它足够小小到你可以把每一步都摊在纸上推演清楚没有任何黑盒同时又足够典型典型到三指针、去重、多路归并这些东西在后来的很多题目里都会反复出现。把它彻底吃透比盲目地再刷十道简单题有用得多。
阅读完成 · 觉得有帮助？
