Java動態(tài)規(guī)劃之丑數(shù)問題實(shí)例講解
問題描述：
我們把只包含質(zhì)因子 2、3 和 5 的數(shù)稱作丑數(shù)（Ugly Number）。求按從小到大的順序的第 n 個(gè)丑數(shù)。
注： 1也是丑數(shù)
思路：
我們來分析一下丑數(shù)如何得到，肯定是由前面的丑數(shù)乘2，乘3或者乘5得到，因此這是一道動態(tài)規(guī)劃題。
- 使用 dp[i] 記錄第i個(gè)丑數(shù)， 初始值dp[0] = 1，返回 dp[n-1]
- 使用 a，b，c 記錄以及 2，3，5 分別乘到了第幾個(gè)丑數(shù)
- 動態(tài)規(guī)劃方程為：
dp[i] = Math.min(Math.min(dp[a]*2, dp[b]*3), dp[c]*5);
如何更新a，b，c：
- 若當(dāng)前丑數(shù)（上述最小值）為dp[a]*2，則 a++
- 若當(dāng)前丑數(shù)（上述最小值）為dp[b]*3，則 b++
- 若當(dāng)前丑數(shù)（上述最小值）為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];
}
}
變式題
題目描述：
有些數(shù)的素因子只有 3，5，7，請?jiān)O(shè)計(jì)一個(gè)算法找出第 k 個(gè)數(shù)。注意，不是必須有這些素因子，而是必須不包含其他的素因子。例如，前幾個(gè)數(shù)按順序應(yīng)該是 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];
}
}
到此這篇關(guān)于Java動態(tài)規(guī)劃之丑數(shù)問題實(shí)例講解的文章就介紹到這了,更多相關(guān)Java丑數(shù)問題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了Java跳出多重嵌套循環(huán)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
Java?Thread.currentThread().getName()?和?this.getName()區(qū)別詳
本文主要介紹了Thread.currentThread().getName()?和?this.getName()區(qū)別詳解，TestThread?testThread?=?new?TestThread();2022-02-02
SpringBoot隨機(jī)端口啟動的實(shí)現(xiàn)
本文主要介紹了SpringBoot隨機(jī)端口啟動的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-07-07
MyBatisPlus使用@TableField注解處理默認(rèn)填充時(shí)間的問題
這篇文章主要介紹了MyBatisPlus使用@TableField注解處理默認(rèn)填充時(shí)間的問題，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-01-01
Spring實(shí)現(xiàn)HikariCP連接池的示例代碼
在SpringBoot 2.0中，我們使用默認(rèn)連接池是HikariCP，本文講一下HikariCP的具體使用，具有一定的參考價(jià)值，感興趣的可以了解一下2021-08-08
Spring中的singleton和prototype的實(shí)現(xiàn)
這篇文章主要介紹了Spring中的singleton和prototype的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
這篇文章主要介紹了Eclipse在線安裝hibernate插件，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2019-04-04
這篇文章主要介紹了淺談java中字節(jié)與字符的區(qū)別，字節(jié)是java中的基本數(shù)據(jù)類型，用來申明字節(jié)型的變量；字符是語義上的單位，它是有編碼的，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
這篇文章主要介紹了Spring中Bean的單例和多例使用說明，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-06-06
這篇文章主要給大家介紹了一些關(guān)于你可能并不了解的java枚舉的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09