JavaScript中的动态规划

动态规划将问题分解成越来越小的子问题。这些子问题并不是独立解决的。相反，这些较小子问题的结果会被记住并用于类似或重叠的子问题。

动态规划用于解决可以分解成类似子问题的问题，以便可以重用其结果。通常，这些算法用于优化。在解决手头的子问题之前，动态算法会尝试检查先前解决的子问题的结果。子问题的解决方案被组合起来以实现最佳解决方案。

要使用动态规划解决问题，

• 问题应该能够分解成较小的重叠子问题。
• 可以通过使用较小子问题的最优解来获得最优解。
• 动态算法使用记忆化。

动态规划问题可以使用两种方法解决 -

• 自底向上动态规划：在这种方法中，我们首先分析问题并查看解决子问题的顺序。我们从解决琐碎的子问题开始，逐步构建到给定的问题。

• 自顶向下动态规划：在这种方法中，我们从分解给定问题开始解决它。如果您发现某个给定的子问题已经被解决，则只需返回存储的解决方案。

Samual Sam

更新于: 2019年7月30日

2K+ 阅读量

开启你的职业生涯

通过完成课程获得认证

开始学习