題意
求第i個un， 定義un：質因數只包含2,3,5的數。
思路
算法1：
狀態表示：d[i]，第i個UN
轉移方程：d[i]=min0≤j1,j2,j3<i{2d[j1],3d[j2],5d[j3]}且d[i]>d[i?1]
時間復雜度：O(n2)
算法2
因為我們的UN一定只以2,3,5作為質因數，其實就是之前的某個UN*2或*3或*5后最小的那個數。
于是，我們只需要設置3個指針t2,t3,t5，例如t2代表：我們t2指向的數*2來得到下一個UN。
所以，我們可以遞推出第i個UN為：min{2dt2,3dt3,5dt5}。然后根據我們的選擇將指針后挪一位。
細節
中間過程會爆int，所以注意用long long
代碼
//algorithm 1#define LL long longconst int maxn = 2000;LL d[maxn];class Solution {public: int nthUglyNumber(int n) { for (int i = 0; i <= n; i++) d[i] = INT_MAX; d[1] = 1, d[2] = 2, d[3] = 3, d[4] = 4, d[5] = 5; for (int i = 6; i <= n; i++) { for (int j = 2; j <= i - 1; j++) { if (d[j] * 2 > d[i - 1]) d[i] = min(d[i], d[j] * 2); if (d[j] * 3 > d[i - 1]) d[i] = min(d[i], d[j] * 3); if (d[j] * 5 > d[i - 1]) d[i] = min(d[i], d[j] * 5); } } return (int)d[n]; }};//algorithm 2class Solution {public: int nthUglyNumber(int n) { vector<long long> d(n + 1, 0); int t2 = 1, t3 = 1, t5 = 1; d[1] = 1; for (int i = 2; i <= n; i++) { d[i] = min(d[t2] * 2, min(d[t3] * 3, d[t5] * 5)); if (d[i] == d[t2] * 2) t2++; if (d[i] == d[t3] * 3) t3++; if (d[i] == d[t5] * 5) t5++; } return (int)d[n]; }};
