醜い番号 - DPアプローチ

Question

質問： 醜い番号は、唯一の素因数がシーケンス1、2、3、4、5、6、8、9、10、12 2、3または5である数であります15、...は最初の11の醜い数字を示しています。慣例により、1が含まれています。

数字nが与えられた場合、タスクはn’th醜い番号を見つけることです。 （https://www.geeksforgeeks.org/ugly-numbers/）

回答：上記のリンクでの動的プログラミングアプローチ

擬似コード：

1 Declare an array for ugly numbers: ugly[n] 
2 Initialize first ugly no: ugly[0] = 1 
3 Initialize three array index variables i2, i3, i5 to point to 
    1st element of the ugly array: 
     i2 = i3 = i5 =0; 
4 Initialize 3 choices for the next ugly no: 
     next_mulitple_of_2 = ugly[i2]*2; 
     next_mulitple_of_3 = ugly[i3]*3 
     next_mulitple_of_5 = ugly[i5]*5; 
5 Now go in a loop to fill all ugly numbers till 150: 
For (i = 1; i < 150; i++) 
{ 
    /* These small steps are not optimized for good 
     readability. Will optimize them in C program */ 
    next_ugly_no = Min(next_mulitple_of_2, 
         next_mulitple_of_3, 
         next_mulitple_of_5); 

    ugly[i] = next_ugly_no  

    if (next_ugly_no == next_mulitple_of_2) 
    {    
     i2 = i2 + 1;   
     next_mulitple_of_2 = ugly[i2]*2; 
    } 
    if (next_ugly_no == next_mulitple_of_3) 
    {    
     i3 = i3 + 1;   
     next_mulitple_of_3 = ugly[i3]*3; 
    }    
    if (next_ugly_no == next_mulitple_of_5) 
    {  
     i5 = i5 + 1;   
     next_mulitple_of_5 = ugly[i5]*5; 
    } 

}/* end of for loop */ 
6.return next_ugly_no 

疑問：

私はDPのアプローチを理解していませんこの場合。

1. サブ問題は何ですか？
2. この場合の再帰とは何ですか？
3. サブ問題はどのように重なっていますか？

4. なぜ私たちは現在の醜い番号を追跡するのですか？なぜ2,3,5の倍数を通過するのではなく、各点を最小限にとどめてください。

   2,3,5と同様です。次に、それぞれの倍数をインクリメントする4,3,5、そして4,6,5 ...キーを押します。

関連質問：nth ugly number（。私は答えてweentが、私は、私が言及した上記の質問で混乱していた）

Answer 1

1. 部分問題：3の2の倍数であるすべての数字を、見つける、の5
2. 再帰：過去の醜い数字を使用して将来の醜い数字を計算する。ダイナミックプログラミングソリューションは、ストレージの使用による再帰の必要性を短絡させます。
3. オーバーラップ：出力は数値順である必要がありますので、どのサブ問題が次の順序で次のものを生成するかは不明です。
4. なぜトラックを保持：スペースの削減が醜い配列を剪定することによって達成することができます。前の醜い番号を再利用することなく、あなただけの指数は2^nは、3^nは、5^nは

さらなる最適化を結果になるだろう再び必要ではないので、<分（i2、i3、i5）の値をすべて解除します。