Write a program to find the

`n`

-th ugly number.Ugly numbers are positive numbers whose prime factors only include

`2, 3, 5`

. For example,`1, 2, 3, 4, 5, 6, 8, 9, 10, 12`

is the sequence of the first`10`

ugly numbers.Note that

`1`

is typically treated as an ugly number.Hint:

- The naive approach is to call
`isUgly`

for every number until you reach the nth one. Most numbers arenotugly. Try to focus your effort on generating only the ugly ones.- An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
- The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.
- Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 * 2, L2 * 3, L3 * 5).
Credits:

Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

dynamic programming.

class Solution { public: int nthUglyNumber(int n) { long dp[n + 1]; dp[1] = 1; for(int i = 2; i <= n ;i++){ long prevBiggest = dp[i - 1]; long ans = dp[i - 1] * 5; for(int j = i - 1; j >= 1; j--){ if(dp[j] * 5 < dp[i - 1]) break; if(dp[j] * 5 > dp[i - 1] && dp[j] * 5 < ans){ ans = dp[j] * 5; } if(dp[j] * 3 > dp[i - 1] && dp[j] * 3 < ans){ ans = dp[j] * 3; } if(dp[j] * 2 > dp[i - 1] && dp[j] * 2 < ans){ ans = dp[j] * 2; } } dp[i] = ans; } return (int)dp[n]; } };