丑陋的数字 - DP方法

Question

问题：丑陋的数字是唯一的素因子为2,3或5的数字。序列1,2,3,4,5,6,8,9,10,12,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..keeps增加每个的倍数。

相关问题：qazxsw poi（我仔细阅读了答案，但我对上面提到的问题感到困惑。）

Answer 1

1. subproblems：查找所有数字为2的倍数，3，为5
2. 递归：使用以前的丑陋数字来计算未来的丑陋数字。动态编程解决方案通过使用存储来缩短递归的需要。
3. 重叠：输出需要按数字顺序排列，因此不清楚哪个子问题将按顺序生成下一个子问题。
4. 为什么要跟踪：没有重复使用以前的丑陋数字，你只能获得指数结果2 ^ n，3 ^ n，5 ^ n

进一步优化：通过修剪丑陋的数组来取消设置任何<min（i2，i3，i5）的值，因为它们将永远不再需要，可以实现空间缩减。