丑数 - dp 的数学直觉

我正在尝试找到“丑陋”的数字，这是一系列唯一质因数为 [2,3,5] 的数字。

我找到了动态规划解决方案，并想了解它是如何工作的以及逻辑背后的数学直觉是什么。

1. 该算法是为 2、3 和 5 的倍数保留三个不同的计数器变量。让我们假设 i2、i3 和 i5。

2. 声明丑陋数组并将 0 索引初始化为 1，因为第一个丑陋数字是 1。

3. 初始化i2=i3=i4=0；

4. ugly[i] = min(ugly[i2]*2,ugly[i3]*3,ugly[i5]*5) 并递增 i2 或 i3 或 i5 所选择的索引。

Dry run:

ugly = |1|

  i2=0;
  i3=0;
  i5=0;

ugly[1] = min(ugly[0]*2, ugly[0]*3, ugly[0]*5) = 2

---------------------------------------------------

ugly = |1|2|

  i2=1;
  i3=0;
  i5=0;

ugly[2] = min(ugly[1]*2, ugly[0]*3, ugly[0]*5) = 3

---------------------------------------------------

ugly = |1|2|3|

  i2=1;
  i3=1;
  i5=0;

ugly[3] = min(ugly[1]*2, ugly[1]*3, ugly[0]*5) = 4

---------------------------------------------------

ugly = |1|2|3|4|

  i2=2;
  i3=1;
  i5=0;

ugly[4] = min(ugly[2]*2, ugly[1]*3, ugly[0]*5) = 5

---------------------------------------------------

ugly = |1|2|3|4|5|

  i2=2;
  i3=1;
  i5=1;

ugly[4] = min(ugly[2]*2, ugly[1]*3, ugly[0]*5) = 6

---------------------------------------------------

ugly = |1|2|3|4|5|6|

我不明白如何从 2 的索引形成 6。有人可以用简单的方式解释吗？

每个“丑”数（1 除外）都可以通过将一个较小的丑数乘以 2、3 或 5 来形成。

假设到目前为止发现的难看的数字是[1,2,3,4,5]。根据该列表，我们可以生成三个丑陋数字序列：

乘以 2，可能的丑数是 [2,4,6,8,10]
乘以 3，可能的丑数是 [3,6,9,12,15]
乘以 5，可能的丑数是 [5,10,15,20,25]

但是列表中已经有 2、3、4 和 5，因此我们不关心小于或等于 5 的值。让我们用 a 标记这些条目-表明我们不关心他们

乘以 2，可能的丑数是 [-,-,6,8,10]
乘以 3，可能的丑数是 [-,6,9,12,15]
乘以 5，可能的丑数是 [-,10,15,20,25]

事实上，我们真正关心的是smallest每个序列中的数字

乘以2，大于5的最小数是6
乘以3，大于5的最小数是6
乘以5，大于5的最小数是10

将 6 添加到丑数列表后，每个序列都多了一个元素：

乘以 2，可能的丑数是 [-,-,-,8,10,12]
乘以 3，可能的丑数是 [-,-,9,12,15,18]
乘以 5，可能的丑数是 [-,10,15,20,25,30]

但每个序列中有用的元素是：

乘以2，大于6的最小数是8
乘以3，大于6的最小数是9
乘以5，大于6的最小数是10

所以你可以看到算法正在做的是创建三个丑陋的数字序列。每个序列都是通过将所有现有的丑数乘以三个因子之一而形成的。

但我们关心的是每个序列中最小的数字（大于迄今为止发现的最大的丑数）。

因此索引 i2、i3 和 i5 是对应序列的索引。当您使用序列中的数字时，您将更新索引以指向该序列中的下一个数字。