1
2
3

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

1
2
3

输入：n = 1
输出：1
解释：1 通常被视为丑数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

struct Solution;

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 数学法
    pub fn nth_ugly_number(n: i32) -> i32 {
        let n = n as usize;
        let (mut c2, mut c3, mut c5) = (0, 0, 0);
        let mut dp = vec![1; n];
        for i in 1..n {
            dp[i] = vec![dp[c2] * 2, dp[c3] * 3, dp[c5] * 5]
                .into_iter()
                .min()
                .unwrap();
            if dp[i] == dp[c2] * 2 {
                c2 += 1;
            }
            if dp[i] == dp[c3] * 3 {
                c3 += 1;
            }
            if dp[i] == dp[c5] * 5 {
                c5 += 1;
            }
        }
        dp[n - 1]
    }
}
// @lc code=end