题目描述

题解

动态规划

首先想到的就是用动态规划来做, 因为有一个确定的规律: 某一个丑数, 一定是由之前的某个丑数乘以2,或者乘以3, 或者乘以5求得的.

有了这个关系, 直接往动态规划上想.

接下来只需要考虑如何从之前的丑数得出所求的丑数.根据刚才提出的思路, 可知:

已知n个丑数x1, x2, …, xn, 要得出xn+1, 一定是以下三种情况之一:

然后继续分析, 索引a, b, c需要满足以下条件:

则可以通过递推公式求出第n+1个丑数:

public int nthUglyNumber(int n) {
    if (n == 0) {
        return 0;
    }

    int[] dp = new int[n];
    dp[0] = 1;
    int a = 0;
    int b = 0;
    int c = 0;

    for (int i = 1; i < n; i++) {

        dp[i] = Math.min(Math.min(dp[a] * 2, dp[b] * 3), dp[c] * 5);
        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];

}