264. Ugly Number II

本题也是不难，就是有点巧，我用heap的方法做了出来，但是本题的最优解肯定是dynamic programming，所以又重新解了一遍。本题不准备过多描述，解释其实不好解释，代码是一看就懂。需要注意：

• 同时使用4个index：2，3，5，和综合的。显而易见，5的增常最慢

• 对于同一个global index，即同一个number，可能有和两种可能，所以，2和5的index需要同时增加

• 时间复杂度：

• 空间复杂度:

代码如下：

class Solution {
  public int nthUglyNumber(int n) {
    int index2 = 0;
    int index3 = 0;
    int index5 = 0;
    int[] dp = new int[n];
    dp[0] = 1;
    for (int idx = 1; idx < n; ++idx) {
      int num2 = 2 * dp[index2];
      int num3 = 3 * dp[index3];
      int num5 = 5 * dp[index5];
      int minVal = Math.min(num2, Math.min(num3, num5));
      if (minVal == num2) {
        dp[idx] = num2;
        ++index2;
      }
      if (minVal == num3) {
        dp[idx] = num3;
        ++index3;
      }
      if (minVal == num5) {
        dp[idx] = num5;
        ++index5;
      }
    }
    return dp[n-1];
  }
}