剑指 Offer 49. 丑数

---

---

题目

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

思考

1、丑数，就是前面的数通过2或3或*5得到的数
2、这题使用动态规划，动态方程
dp[i] = Math.min(Math.min(dp[a]*2,dp[b]*3),dp[c]*5);

代码和注释

class Solution {
    // 使用动态规划
    public int nthUglyNumber(int n) {
        // 定义状态数组
        int[] dp = new int[n+1];
        // 初始状态
        int a = 1, b =1, c = 1;
        dp[1] = 1;
        for(int i = 2; i<=n; i++){
            dp[i] = Math.min(Math.min(dp[a]*2,dp[b]*3),dp[c]*5);
            // 判断选择哪一个
            if(dp[i] == dp[a] * 2){
                a++;
            }
            if(dp[i] == dp[b] * 3){
                b++;
            }
            if(dp[i] == dp[c] * 5){
                c++;
            }
        }
        return dp[n]; 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

总结

1、最难的点还是在于识别动态规划的题型
2、那么动态规划的方程是重点