动态规划:从新手到专家 Hawstein

作者：Hawstein 出处：http://hawstein.com/posts/dp-novice-to-advanced.html 什么是动态规划，我们要如何描述它? 动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度，因此它比回溯法、暴力法等要快许多。 现在让我们通过一个例子来了解一下DP的基本原理。 首先，我们要找到某个状态的最优解，然后在它的帮助下，找到下一个状态的最优解。