解法一

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

  1. class Solution {
  2.     public int nthUglyNumber(int n) {
  3.         // dp[i]表示第i+1个丑数
  4.         int[] dp = new int[n];
  5.         dp[0] = 1;
  6.         int a = 0, b = 0, c = 0;
  7.         int x1 = dp[a] * 2;
  8.         int x2 = dp[b] * 3;
  9.         int x3 = dp[c] * 5;
  10.         for (int i = 1; i < n; ++i) {
  11.             dp[i] = Math.min(Math.min(x1, x2), x3);
  12.             // 要分开判断, 防止重复的值多次计入
  13.             if (dp[i] == x1) {
  14.                 ++a;
  15.                 x1 = dp[a] * 2;
  16.             }
  17.             if (dp[i] == x2) {
  18.                 ++b;
  19.                 x2 = dp[b] * 3;
  20.             }
  21.             if (dp[i] == x3) {
  22.                 ++c;
  23.                 x3 = dp[c] * 5;
  24.             }
  25.         }
  26.         return dp[n - 1];
  27.     }
  28. }