是否经常听到朋友论述「我们公司正在尝试DP」、「想要成为一个好的程序员，你需要精通DP」等等，相信你一定也有质疑DP到底是什么的疑惑。下面我们一起来深入探究！
DP的概念DP的全名是Dynamic Programming，即动态规划。DP是一种解决问题的方案，一般来说，一个问题只要满足以下两个条件，就可以使用DP来解决：
1. 最优解性质：在问题的多个解法中，一定存在一种解法是最优的；
2. 无后效性：即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
如果一个问题满足了以上两个条件，那么我们就可以考虑使用DP来解决。
DP的应用场景DP算法的应用非常广泛，以下是一些常见的应用场景：
- 最长公共子序列
- 最小编辑距离
- 最优二叉搜索树
- 背包问题
- 矩阵连乘问题
相比于暴力解决问题，DP算法的时间复杂度更低。而相比于贪心算法，DP可以得到全局最优解而不是局部最优解。
DP的缺点相比于递归算法，DP的空间复杂度更高。
总结DP是一种解决问题的有效方式，解决许多需要求最优解的问题，是程序员必须掌握的一种算法。
