醜數 II

​​https://leetcode-cn.com/problems/ugly-number-ii/​​

給你一個整數 n ，請你找出并傳回第 n 個 醜數 。

**醜數 **就是隻包含質因數 2、3 和/或 5 的正整數。

**輸入：**n = 10 **輸出：**12 解釋：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 個醜數組成的序列。

**輸入：**n = 1 **輸出：**1 **解釋：**1 通常被視為醜數。

條件

• 1 <= n <= 1690

這道題首先想到的思路是打表，在編寫代碼的時候輸出所有的醜數，然後再放到答案中即可。不過，這道題目是放在動态規劃中等難度的題目裡面的，想一個動态規劃的解決方案才是正解。

那麼，我們來思考一下，從題目中得知，醜數一定隻有2、3和5這幾個質因數，那麼就可以推斷出，醜數一定是醜數本身的乘積，那麼我們可以構造出一個一維動态規劃數組dp，dp[n-1]就是需要的結果，而dp[i]的遞推關系就是由0~i-1的dp結果與2、3和5乘積的最小值（這裡可以再做一個dp，不過就算是二重循環這裡的時間複雜度也是足夠的，是以不需要維護也行）即可。

class Solution {
    public int nthUglyNumber(int n) {
        long[] dp = new long[n + 10];
        dp[0] = 1;
        dp[1] = 2;
        dp[2] = 3;
        dp[3] = 4;
        dp[4] = 5;
        int[] x = new int[]{2, 3, 5};
        for (int i = 5; i <= n; i++) {
            long tmp = dp[i - 1];
            long lowest = -1;
            for (int j = 0; j < i; j++) {
                for (int k = 0; k < 3; k++) {
                    long a = dp[j] * x[k];
                    if (a > tmp) {
                        if (lowest == -1) {
                            lowest = a;
                        } else {
                            lowest = Math.min(lowest, a);
                        }
                    }
                }
            }
            dp[i] = lowest;
        }

        return new Long(dp[n-1]).intValue();
    }
}