一尘不染

动态编程的记忆化或列表化方法

algorithm

使用动态编程可以解决许多问题,例如最长子序列增加。这个问题可以通过两种方法解决

  1. 备注(自上而下)-使用递归解决子问题并将结果存储在某些哈希表中。
  2. 制表(自下而上)-使用迭代方法来解决问题,方法是先解决较小的子问题,然后在执行较大的问题时使用它。

我的问题是,就时间和空间复杂度而言,哪种方法更好?


阅读 231

收藏
2020-07-28

共1个答案

一尘不染

简短的答案: 这取决于问题!

记忆化 通常需要更多的代码,是那么直接,但在一些问题计算的优势,主要是那些你 并不 需要计算整个矩阵的所有值达到了答案。

制表 更直接,但可能会计算不必要的值。但是,如果确实需要计算所有值,则此方法通常会更快,因为开销较小。

2020-07-28