【面试题】丑数（动态规划）

题目描述

解题思路

根据丑数的定义， 丑数应该是另⼀个丑数乘以 2、 3或者 5的结果（1除外），满足递推性质 。 因此我们可以创建⼀个数组， ⾥⾯的数字是排好序的丑数， 每⼀个丑数都是前⾯的丑数乘以 2、 3或者 5得到的。

Java

动态规划法

class Solution {
    public int nthUglyNumber(int n) {
        if(n <= 0) return 0;
        int[] dp = new int[n]; // 定义状态表，dp[i]代表第 i + 1 个丑数。
        int a = 0, b = 0, c = 0;
        dp[0] = 1; // 第一个丑数为 1
        for(int i=1; i<dp.length; i++) {
            dp[i] = Math.min(Math.min(dp[a]*2, dp[b]*3), dp[c]*5);
            // 分别判断dp[i]与dp[a]*2，dp[b]*3，dp[c]*5的大小关系，若相等则将对应索引 a,b,c 加1
            // 这里不采用if-else的原因是，存在2*某个丑数 ,3*某个丑数,5*某个丑数相同的情况。当有多个索引满足条件时，均要+1
            if(dp[a]*2 == dp[i]) a++;
            if(dp[b]*3 == dp[i]) b++;
            if(dp[c]*5 == dp[i]) c++;
        }
        return dp[n-1]; // 返回第 n 个丑数
    }
}

参考

https://leetcode-cn.com/problems/chou-shu-lcof/solution/mian-shi-ti-49-chou-shu-dong-tai-gui-hua-qing-xi-t/