Java中如何通过动态规划解决丑数问题实例演示？

本文共计856个文字，预计阅读时间需要4分钟。

题目描述：编写一个函数，输入仅包含质因子2、3和5的数（Ugly Number）。要求按从小到大的顺序输出第n个丑数。

思路：分析丑数如何得到，可以确定是由前面的丑数乘以2、3、5得到的。例如，第一个丑数是1，第二个丑数是2，第三个丑数是3，第四个丑数是4，第五个丑数是5，第六个丑数是6，第七个丑数是8，以此类推。

代码实现：可以使用动态规划的方法，定义一个数组来存储前n个丑数，然后从第二个数开始，每次循环分别乘以2、3、5，取这三个乘积的最小值，作为下一个丑数。

pythondef get_ugly_number(n): ugly_numbers=[1] * n i2, i3, i5=0, 0, 0 for i in range(1, n): min_ugly=min(ugly_numbers[i2] * 2, ugly_numbers[i3] * 3, ugly_numbers[i5] * 5) ugly_numbers[i]=min_ugly if min_ugly==ugly_numbers[i2] * 2: i2 +=1 if min_ugly==ugly_numbers[i3] * 3: i3 +=1 if min_ugly==ugly_numbers[i5] * 5: i5 +=1 return ugly_numbers[-1]

n=10print(get_ugly_number(n))

输出：10

问题描述：

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

注： 1也是丑数

思路：

我们来分析一下丑数如何得到，肯定是由前面的丑数乘2，乘3或者乘5得到，因此这是一道动态规划题。

1. 使用 dp[i] 记录第i个丑数， 初始值dp[0] = 1，返回 dp[n-1]
2. 使用 a，b，c 记录以及 2，3，5 分别乘到了第几个丑数
3. 动态规划方程为：

dp[i] = Math.min(Math.min(dp[a]*2, dp[b]*3), dp[c]*5);

如何更新a，b，c：

• 若当前丑数（上述最小值）为dp[a]*2，则 a++
• 若当前丑数（上述最小值）为dp[b]*3，则 b++
• 若当前丑数（上述最小值）为dp[c]*5，则 c++

图解：

代码：

class Solution { public int nthUglyNumber(int n) { int a=0, b=0, c=0; int[] dp = new int[n]; dp[0] = 1; for(int i=1; i<n; i++){ int n1 = dp[a]*2; int n2 = dp[b]*3; int n3 = dp[c]*5; dp[i] = Math.min(Math.min(n1, n2), n3); if(dp[i] == n1){ a++; } if(dp[i] == n2){ b++; } if(dp[i] == n3){ c++; } } return dp[n-1]; } }

变式题

题目描述：

有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。

思路

本题和前面的题一样，只要把 2，3，5 改成 3，5，7即可 代码

class Solution { public int getKthMagicNumber(int k) { int a=0, b=0, c=0; int[] dp = new int[k]; dp[0] = 1; for(int i=1; i<k; i++){ int n1 = dp[a]*3; int n2 = dp[b]*5; int n3 = dp[c]*7; dp[i] = Math.min(Math.min(n1, n2), n3); if(dp[i] == n1){ a++; } if(dp[i] == n2){ b++; } if(dp[i] == n3){ c++; } } return dp[k-1]; } }

到此这篇关于Java动态规划之丑数问题实例讲解的文章就介绍到这了,更多相关Java丑数问题内容请搜索自由互联以前的文章或继续浏览下面的相关文章希望大家以后多多支持自由互联！