JZ33 丑数

本文最后更新于：2022年4月9日 中午

image-20211008105133475

Solution

  • 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if (index < 7) return index;
        int two = 1, three = 1, five = 1;  // 1 * 2^0, 1 * 3^0, 1 * 5^0
        // dp 数组，dp[i] 表示第 i 个丑数
        vector<int> dp(index + 1, 0);
        dp[1] = 1;
        for (int i = 2; i <= index; ++i) {
            int n1 = dp[two] * 2, n2 = dp[three] * 3, n3 = dp[five] * 5;
            dp[i] = min(n1, min(n2, n3));
            if (dp[i] == n1) ++two;
            if (dp[i] == n2) ++three;
            if (dp[i] == n3) ++five;
        }
        return dp[index];
    }
};