在动态编程中，我是否总是必须填写整个表？

Question

[执行dynamic programming时，我通常会急切地填写表格（从下到上，而不是使用自上而下的递归）。这将导致嵌套循环填充表中的所有值。

我是否总是必须填满整个桌子？

示例DP任务：

计算字符串hello和world之间的距离：

  h e l l o
w 1 2 3 4 5
o 2 2 3 4 5
r 3 3 3 4 5
l 4 4 3 3 4
d 5 5 4 4 4

上面的示例（希望我没有出错）比较了hello和world的每个子字符串并存储了它们的差异。例如。 he和wor之差为3。进一步的计算基于所存储的结果。

真的有必要比较每个子字符串吗？

Answer 1

有时不是。对于某些DP问题，绝不会使用大量状态，因此您不必计算所有状态。一种利用此方法的方法是使用memoization。您定义一个计算DP状态的函数。该函数首先检查该状态是否已经计算。如果不是，它将使用递归计算该状态。这样，仅会计算实际使用的状态。