问求解问题的动态规划技术

EN

每个动态规划问题都可以表示为递推关系，它可以用recursion+memoization来求解，可以转化为tabulation+iteration。

当使用表格解决DP问题时，通常通过填充n维表来解决自下而上的问题()。然后根据表中的结果，计算出原问题的解。

当您使用回忆录解决一个DP问题时，您可以通过维护已经解决的子问题的地图来解决它。您这样做自上而下的，这意味着您首先解决了"top“问题(这通常是递归地解决子问题)。

使用tabulation+iteration的DP问题的时间复杂度与该解决方案的转换、等效和正确的memoization+recursion版本相同。在tabulation+iteration方法中，通常很容易找到时间复杂度。另一方面，memoization+recursion版本的DP解决方案更直观和可读性更强。