【原】Python | 動態(tài)規(guī)劃解決“返回第n個丑數(shù)”

給你一個整數(shù) n ，請你找出并返回第 n 個 丑數(shù) 。丑數(shù) 就是只包含質(zhì)因數(shù) 2、3 和/或 5 的正整數(shù)。

 示例 1：

輸入：n = 10

輸出：12

解釋：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 個丑數(shù)組成的序列。

示例 2：

輸入：n = 1

輸出：1

解釋：1 通常被視為丑數(shù)。

解決本題要用到的是動態(tài)規(guī)劃，同時要先知道什么是丑數(shù)，題目也很明確的說明了丑數(shù)是什么，接下來就是實現(xiàn)在代碼方面找到丑數(shù)，對于找丑數(shù)可以使用python的一次循環(huán)遍歷就可以得到需要的丑數(shù)，因為只存在2,3,5這三個元素，遍歷過程中不會太復雜；知道了如何判斷丑數(shù)后就是進一步的丑數(shù)的變形方式，本題所使用的動態(tài)規(guī)劃并不是太復雜的動態(tài)規(guī)劃，這里要用到的新的變量“指針”（p2,p3,p5）此處pi是可以與i相乘的最小丑數(shù)的位置，設置了三個指針后從最小的開始，指針的移動表示在從大到小的尋找丑數(shù)，nums[i]是由三個指針乘以相應的數(shù)得到的，把相對應的pi + 1表示沒有乘過次nums的最小丑數(shù)變大了，然后一個數(shù)一個數(shù)的加進數(shù)組中，直到遍歷結束。

具體代碼如下：

運行效果：

雖然是使用了動態(tài)規(guī)劃的方式解決了本題，但對與動態(tài)規(guī)劃還是處于模糊狀態(tài)，還是會繼續(xù)學習關于動態(tài)規(guī)劃的知識，盡快熟悉并掌握運用，同時，做本題是要有一個清晰的思路，先得到什么，然后再做一步怎么樣的操作。

實習編輯：李欣容