# 第 2 节动态规划用于解决怎样的问题

# 解决有大量重复子问题的特定问题

我们学习的很多算法与数据结构，都是用于解决特定的问题。动态规划也不例外。

那么，动态规划用于解决怎样的问题呢。动态规划解决的子问题有一个非常明显的特点：有大量重复子问题。大家可以做一做动态规划的入门问题：斐波拉契数列（「力扣」第 509 题）。

空间换时间：把重复求解的子问题的结果记录下来，这是很自然且普遍的做法，用空间换时间。

如果子问题没有重复，每个问题只求解一次，那是「分治算法」，也不需要记忆化，直接用编程语言的方法栈保存临时结果就可以完成计算。

在填表的过程中，一定会有「数据汇总」。那么什么叫「数据汇总」呢，就是 Excel 表格里的 sum、average、count。

所以使用动态规划解决的问题，通常只会问最大值、最小值、方案有多少种，即 只需要给出结果，而不需要给出结果是怎么来来的。

只记录子问题的结果：这是因为动态规划在求解问题的过程中，实际上需要解决原始问题的所有子问题。如果把这些子问题的求解过程都记录下来，不仅有空间消耗，还有时间消耗。所以使用动态规划解决的问题通常只需要记录子问题的结果。

有一种算法叫「回溯算法」，它就可以得到一个问题的所有具体解，它通过 深度优先遍历 的方式，在遍历的同时收集 所有我们需要的所有具体解，以后我们再和大家专门介绍。

下一节，我们为大家归纳「动态规划」的算法设计思想。

作者：liweiwei1419 链接：https://suanfa8.com/dynamic-programming/application 来源：算法吧著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。