为什么这个时间复杂度是O(total*n)呢？
Why is this time complexity O(total*n)?
即我无法理解为什么在最坏的情况下 运行 蓝色部分需要 (total⋅n⋅2)+1 步。
函数代码如下：
找到此屏幕截图的视频。
我没有看你链接的视频。但是，查看代码，这看起来像是在计算使用数组 arr.
给出的面额硬币来组成值 total 的不同方法的数量
函数 dp 本质上是用值填充字典 mem。字典 mem 由 total 和 i 索引。在递归调用中，total 和 i 可能（并且将会）变小。 total 采用的新值将在 [0; total] 范围内。 i 取的新值将在 [0; arr.length - 1].
范围内
因此字典可能的不同键数最多为(total+1) * arr.length
使用已经在字典中的一对 total 和 i 的值调用 dp 不会导致进一步的递归调用。因此，导致进一步递归调用的 dp 的调用次数最多为 (total+1) * arr.length.
由于每次调用 dp 最多导致 2 次进一步的递归调用，因此对 dp 的调用总数最多为 2 * (total+1) * arr.length。即 O(total * arr.length)。我假设这就是你所说的 O(total * n).
即我无法理解为什么在最坏的情况下 运行 蓝色部分需要 (total⋅n⋅2)+1 步。
函数代码如下：
我没有看你链接的视频。但是，查看代码，这看起来像是在计算使用数组 arr.
total 的不同方法的数量
函数 dp 本质上是用值填充字典 mem。字典 mem 由 total 和 i 索引。在递归调用中，total 和 i 可能（并且将会）变小。 total 采用的新值将在 [0; total] 范围内。 i 取的新值将在 [0; arr.length - 1].
因此字典可能的不同键数最多为(total+1) * arr.length
使用已经在字典中的一对 total 和 i 的值调用 dp 不会导致进一步的递归调用。因此，导致进一步递归调用的 dp 的调用次数最多为 (total+1) * arr.length.
由于每次调用 dp 最多导致 2 次进一步的递归调用，因此对 dp 的调用总数最多为 2 * (total+1) * arr.length。即 O(total * arr.length)。我假设这就是你所说的 O(total * n).