題意
求第i個(gè)un， 定義un：質(zhì)因數(shù)只包含2,3,5的數(shù)。
思路
算法1：
狀態(tài)表示：d[i]，第i個(gè)UN
轉(zhuǎn)移方程：d[i]=min0≤j1,j2,j3<i{2d[j1],3d[j2],5d[j3]}且d[i]>d[i?1]
時(shí)間復(fù)雜度：O(n2)
算法2
因?yàn)槲覀兊腢N一定只以2,3,5作為質(zhì)因數(shù)，其實(shí)就是之前的某個(gè)UN*2或*3或*5后最小的那個(gè)數(shù)。
于是，我們只需要設(shè)置3個(gè)指針t2,t3,t5，例如t2代表：我們t2指向的數(shù)*2來(lái)得到下一個(gè)UN。
所以，我們可以遞推出第i個(gè)UN為：min{2dt2,3dt3,5dt5}。然后根據(jù)我們的選擇將指針后挪一位。
細(xì)節(jié)
中間過(guò)程會(huì)爆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]; }};
