剑指offer. 面试题49. 丑数. 动态规划解法

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

 

int threeMin(int a, int b, int c) {
        return a <= b ? c <= a ? c : a : c <= b ? c : b;
}

int nthUglyNumber(int n) {

        vector<int> dp(n + 1, 0);
        dp[1] = 1;

        int k = 2;
        int p2 = 1, p3 = 1, p5 = 1;
        while (k <= n) {

                while (dp[p2] * 2 <= dp[k - 1]) p2++;
                while (dp[p3] * 3 <= dp[k - 1]) p3++;
                while (dp[p5] * 5 <= dp[k - 1]) p5++;

                dp[k++] = threeMin(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5);
        }
        return dp[n];
}

 清晰明了！