Python 官方文档：入门教程 => 点击学习
问题描述： 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。 注： 1也是丑数 思路： 我们来分析一下丑数如何得到，肯
问题描述：
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
注： 1也是丑数
思路：
我们来分析一下丑数如何得到，肯定是由前面的丑数乘2，乘3或者乘5得到，因此这是一道动态规划题。
dp[i] = Math.min(Math.min(dp[a]*2, dp[b]*3), dp[c]*5);
如何更新a，b，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丑数问题内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
--结束END--
本文标题: Java动态规划之丑数问题实例讲解
本文链接: https://www.lsjlt.com/news/168790.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑，方便收藏和打印～
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
官方手机版
微信公众号
商务合作
0