解决动态规划问题的七个步骤

步骤一：如何识别一个动态规划问题

首先，我们要弄清楚DP本质上只是一种优化技术。DP是一种解决问题的方法，它可以将其分解为更简单的子问题的集合，仅解决一次这些子问题，然后存储其解决方案。下一次出现相同的子问题时，无需重新计算其解，只需查找先前计算的解即可。这节省了计算时间，但以（希望的）适度的存储空间开销为代价。

认识到使用DP可以解决问题是解决该问题的第一步，也是最困难的一步。您想问自己的问题是，您的问题解决方案是否可以表示为类似较小问题的解决方案的函数。

认识到动态编程问题通常是解决它的最困难的步骤。问题解决方案可以表达为类似较小问题的解决方案的函数吗？

步骤二：识别问题变量

现在我们已经确定子问题之间存在某种递归结构。接下来，我们需要根据功能参数来表达问题，并查看其中哪些参数正在更改。通常，在访谈中，您将拥有一个或两个变化的参数，但是从技术上讲，它可以是任意数量。一个一变参数问题的经典示例是“确定第n个斐波那契数”。关于两个参数更改问题的示例是“计算字符串之间的编辑距离”。如果您不熟悉这些问题，请不必担心。

确定更改参数数量的一种方法是列出几个子问题的示例并比较参数。计算不断变化的参数的数量对于确定我们必须解决的子问题的数量很有价值，但是它本身也很重要，可以帮助我们加强对步骤1中递归关系的理解。

确定变化的参数并确定子问题的数量。

步骤三：弄清递归表达式

这是许多人为了编码而急需完成的重要步骤。尽可能清楚地表达递归关系将增强您对问题的理解，并使其他所有事情都更加容易。

一旦确定了递归关系并根据参数指定了问题，这将是自然而然的步骤。问题如何相互联系？换句话说，假设您已经计算了子问题。您将如何计算主要问题？

递归关系：假设您已经计算了子问题，您将如何计算主要问题？

步骤四：确定基准条件

基本案例是一个子问题，它不依赖于任何其他子问题。为了找到此类子问题，您通常需要尝试一些示例，看看您的问题如何简化为较小的子问题，以及在什么时候无法进一步简化。

无法进一步简化问题的原因是，参数之一将成为在问题约束条件下不可能实现的值。

步骤五：确定是要迭代实现还是递归实现

到目前为止，我们谈论步骤的方式可能会让您认为我们应该递归地解决问题。但是，到目前为止，我们所讨论的一切都与您决定以递归还是迭代的方式实施该问题完全无关。在这两种方法中，您都必须确定递归关系和基本案例。

要决定是迭代还是递归，您需要仔细考虑折衷方案。

步骤六：增加备忘录

备忘录是与DP紧密相关的技术。它用于存储昂贵的函数调用的结果，并在再次出现相同的输入时返回缓存的结果。我们为什么要在递归中添加备忘录？我们遇到相同的子问题，这些子问题在没有备忘的情况下会重复计算。这些重复经常导致指数时间复杂性。

在递归解决方案中，添加备忘录应该很简单。让我们看看为什么。请记住，记忆只是函数结果的缓存。有时候，您可能会偏离此定义以挤出一些次要的优化，但是将备忘录作为函数结果缓存是实现它的最直观的方法。

这意味着您应该：

1. 在每个return语句之前将函数结果存储到内存中
2. 在开始执行任何其他计算之前，先在内存中查找函数结果

步骤七：确定时间复杂度

有一些简单的规则可以使动态编程问题的计算时间复杂度容易得多。您需要执行以下两个步骤：

1. 计算状态数–这取决于问题中更改参数的数量
2. 想想每个状态完成的工作。换句话说，如果除一个状态外的所有其他内容都已计算，那么您需要做多少工作才能计算出最后一个状态