动态规划算法

要素剖析

动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列、最小编辑距离等等。

如前所述，动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事：

• 首先，需要你熟练掌握递归思维，只有列出正确的状态转移方程，才能正确地穷举；
• 而且，你需要判断算法问题是否具备最优子结构，是否能够通过子问题的最值得到原问题的最值；
• 另外，动态规划问题存在重叠子问题，如果暴力穷举的话效率会很低，所以需要你使用「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

以上提到的状态转移方程、最优子结构、重叠子问题就是动态规划三要素。在实际的算法问题中，写出状态转移方程是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因。

思维框架

这里提供一个思维框架，辅助你思考状态转移方程：

明确「baseCase」 -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

按这个套路走，最后的解法代码就会是如下的两种框架：

• 自顶向下递归的动态规划

  def dp(状态1, 状态2, ...):
      for 选择 in 所有可能的选择:
          # 此时的状态已经因为做了选择而改变
          result = 求最值(result, dp(状态1, 状态2, ...))
      return result

• 自底向上迭代的动态规划

  # 初始化 base case
  dp[0][0][...] = baseCase
  # 进行状态转移
  for 状态1 in 状态1的所有取值：
      for 状态2 in 状态2的所有取值：
          for ...
              dp[状态1][状态2][...] = 求最值(选择1，选择2...)