Java O(n) DP solution explained.
\n\n/*\n1 -> 1 base case\n2 -> 1 * 2 (from index 0 * 2)\n3 -> 2 * 3 (form index 0 * 3)\n4 -> 2 * 2 (from index 1 * 2)\n5 -> 1 * 5 (from index 0 * 5)\n6 -> 2 * 3
\n```\n/*\n1 -> 1 base case\n2 -> 1 * 2 (from index 0 * 2)\n3 -> 2 * 3 (form index 0 * 3)\n4 -> 2 * 2 (from index 1 * 2)\n5 -> 1 * 5 (from index 0 * 5)\n6 -> 2 * 3 (from index 1 * 3 || index 2 * 2)\n8 -> 4 * 2 (from index 3 * 2)\n9 -> 3 * 3\n10 -> 5 * 2\n12 -> 6 * 2 || 4 * 3\n15 -> 5 * 3\n\n1. All values are derived from some previous value.\n2. Each previous value will for sure be used once.\n3. So for each previous value, we need to check if it can generate\n    current value. And 3 pointers are need each to * 2, 3, 5.\n\ndp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)\nwhere pk is the pointer that times k to get the next ugly number\nand pk++ each time an ugly number can be computed with pk * k.\n*/\nclass Solution {\n    public int nthUglyNumber(int n) {\n        int[] dp = new int[n];\n        dp[0] = 1; // n >= 1 known fact.\n        int p2 = 0, p3 = 0, p5 = 0;\n        for (int i = 1; i < n; i++) {\n            dp[i] = Math.min(Math.min(dp[p2] * 2, dp[p3] * 3), dp[p5] * 5);\n            p2 = (dp[i] == dp[p2] * 2) ? p2 + 1 : p2;\n            p3 = (dp[i] == dp[p3] * 3) ? p3 + 1 : p3;\n            p5 = (dp[i] == dp[p5] * 5) ? p5 + 1 : p5;\n        }\n        return dp[n - 1];\n    }\n}\n```
['Dynamic Programming', 'Java']