动态规划-1

什么是动态规划

动态规划（Dynamic Programming，简称DP）是一种在计算机科学和数学中用于解决最优化问题的方法。它特别适用于能够分解为重叠子问题的问题，并且这些子问题的解决方案可以被存储起来以供后续使用，从而避免重复计算。

简单的说，就是在一个复杂问题中寻找最值的一种方法。

如何寻找最值

最直接最简单的方法就是——穷举，但动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」才能正确地穷举。 以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。