动态规划：从新手到专家

文章预览

原文：TopCoder 译者：Hawstein 译文：hawstein.com/posts/dp-novice-to-advanced.html （点击文末阅读原文即可前往）  前言 我们遇到的问题中，有很大一部分可以用动态规划(简称DP)来解。 解决这类问题可以很大地提升你的能力与技巧，我会试着帮助你理解如何使用DP来解题。 这篇文章是基于实例展开来讲的，因为干巴巴的理论实在不好理解。 注意：如果你对于其中某一节已经了解并且不想阅读它，没关系，直接跳过它即可。 简介(入门) 什么是动态规划，我们要如何描述它? 动态规划算法通常基于一个递推公式及一个或多个初始状态。 当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度， 因此它比回溯法、暴力法等要快许 ………………………………