Leetcode 264: Ugly Number II

 1 public class Solution {
 2     public int NthUglyNumber(int n) {
 3         if (n == 1) return 1;
 4         
 5         var dp = new long[n];
 6         dp[0] = 1;
 7         
 8         for (int i = 1; i < n; i++)
 9         {
10             dp[i] = Int32.MaxValue;
11             for (int j = i - 1; j >= 0; j--)
12             {
13                 if (dp[j] <= dp[i - 1] / 5) break;
14                 
15                 if (dp[j] > dp[i - 1] / 2) 
16                 {
17                     dp[i] = Math.Min(dp[j] * 2, dp[i]);
18                 }
19                 
20                 if (dp[j] > dp[i - 1] / 3) 
21                 {
22                     dp[i] = Math.Min(dp[j] * 3, dp[i]);
23                 }
24                 
25                 if (dp[j] > dp[i - 1] / 5) 
26                 {
27                     dp[i] = Math.Min(dp[j] * 5, dp[i]);
28                 }
29             }
30         }
31         
32         return (int)dp[n - 1];
33     }
34 }