algorithm - Ugly Number - dp 的数学直觉

Question

我正在尝试找到“丑陋”的数字，这是一系列只有质因数是 [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 选择的索引。

试运行:

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。谁能用简单的方式解释一下？

Answer 1

每个“丑数”(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 的值。让我们用 - 标记这些条目以指示我们不关心他们

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

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

乘以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 是对应序列的索引。当您使用序列中的数字时，您更新索引以指向该序列中的下一个数字。