264. Ugly Number II -- 【M】DP / Math
https://leetcode.com/problems/ugly-number-ii/
https://discuss.leetcode.com/topic/21882/my-16ms-c-dp-solution-with-short-explanation/16
91.40% 8ms 时间O(n) DP
public class Solution {
public int nthUglyNumber(int n) {
int[] uglyN = new int[n];
uglyN[0] = 1;
int index2 = 0, index3 = 0, index5 = 0;
for (int i = 1; i < n; i++) {
uglyN[i] = Math.min(uglyN[index2] 2, Math.min(uglyN[index3] 3, uglyN[index5] * 5));
if (uglyN[i] == uglyN[index2] * 2)
index2++;
if (uglyN[i] == uglyN[index3] * 3)
index3++;
if (uglyN[i] == uglyN[index5] * 5)
index5++;
}
return uglyN[n-1];
}
}
**总结：
本质：找到第N个Ugly number. 动规DP。因为第N个是取前面的最小的分别2 3 5得来的Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 2, L2 3, L3 5).