解决问题的动态规划技术

Question

是否可以使用递归+记忆而不是使用tabulation/iteration来解决任何动态规划问题？或者有一些问题必须使用 tabulation/iteration.

我们也可以在使用递归+记忆化解决任何问题时获得相同的时间复杂度（我知道 space 复杂度不同并且存在递归开销成本）。

Answer 1

每个动态规划问题都可以表示为递归关系，可以使用递归+记忆可以转化为制表+迭代.

当您使用制表法解决 DP 问题时，您可以自下而上 解决问题，通常是通过填充 n 维 table。然后根据 table 中的结果计算出原始问题的解。

当您使用记忆解决 DP 问题时，您可以通过维护已解决的子问题的映射来实现。你这样做 自上而下 在你首先解决“顶级”问题的意义上（通常向下递归解决子问题）。

使用制表+迭代的DP问题的时间复杂度与转换后的等效且正确的记忆+递归版本的解决方案相同。通常在制表+迭代的方法中很容易找到时间复杂度。另一方面，记忆化+递归版本的DP方案更加直观易读。