本文共 837 字，大约阅读时间需要 2 分钟。

【题目】

　　把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。因此，前10个丑数是

求按从小到大的顺序的第N个丑数。

【基本思路】

　　暴力解法： 

        这种暴力解法存在大量的重复计算，例如：现在分析12是不是丑数，12/2=6，而6我们已经知道是丑数了，已经不需要向下计算了。因此我们可以记忆化：将丑数记录下来。 

        这个题目有重叠子问题，考虑使用动态规划。我们不妨假设DP[k]表示第k个丑数，这个丑数就等于前面几个丑数*2或者*3或者*5的最小值,并且丑数的位置只会向后移，我们不妨假设三个i j x分别为*2 *3 *5的丑数位置。由此我们可以写出状态转移方程：

                 dp[k] = min{dp[i]*2,dp[j]*3,dp[x]*5}

由此我们可以写出递推的动态规划代码：

import java.util.Scanner;/** * @author: Mr.Hu * @create: 2019-03-01 21:10 */public class Main{    public static void main(String[] args) {        Scanner sc =new Scanner(System.in);        while (sc.hasNextInt()){           int n=sc.nextInt();           int[] dp=new int[n];           int i=0,j=0,x=0;           dp[0]=1;            for (int k = 1; k 

转载地址：https://blog.csdn.net/h2453532874/article/details/88546754 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！