264. Ugly Number II

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note:

1. 1 is typically treated as an ugly number.

2. n does not exceed 1690.

int nthUglyNumber(int n) { // time: O(n); space: O(n)
    if (n <= 0) return 0;
    if (n == 1) return 1;
    vector<int> dp(n, 0);
    dp[0] = 1;
    int t2 = 0, t3 = 0, t5 = 0;
    for (int i = 1; i < n; ++i) {
        dp[i] = min({dp[t2] * 2, dp[t3] * 3, dp[t5] * 5});
        if (dp[i] == dp[t2] * 2) ++t2;
        if (dp[i] == dp[t3] * 3) ++t3;
        if (dp[i] == dp[t5] * 5) ++t5;
    }
    return dp.back();
}