DynamicProgramming，简称DP，这个名字给人的感觉是一个很高大上很复杂的算法。很多同学看到这个名字可能会望而却步，面试的时候也很害怕被问到。动态规划的主题。其实它并不是一个确定的算法，它是一种以最优方式解决问题的思路或方法。它是美国数学家贝尔曼在研究多阶段决策过程的优化问题时提出的。但也有一些与时间无关的静态规划与其对应，如：线性规划、非线性规划等。在运筹学中，动态规划是一个非常重要的内容，在各个行业都有广泛的应用。我们如何理解动态规划？如果一个问题的最优解可以通过它的子问题的最优解推导出来，那么我们可以先求出它的子问题的最优解，然后根据子问题的最优解得到原解问题的解决方案。如果子问题重复次数较多，为了减少重复计算，降低时间复杂度，可以自下而上从最后的子问题逐步求解到原问题，先将子问题存储起来。在求解大的子问题时，可以直接从表中查询子问题的解，这就是动态规划的基本思想。简单的说就是将一个大问题简化为若干个子问题存入一个表中，然后根据数据表中子问题的解求出大问题的解。这个算法是不是很眼熟？其实动态规划类似于分治算法，我们经常将它与分治算法进行比较。它们都需要将其分解为子问题并解决子问题。不同的是，分治算法是自上而下求解子问题，然后将子问题的解组合起来，得到原问题的解；而动态规划是将子问题拆解并组合后，自底向上求解子问题。存储结果存储起来，求解大的子问题时直接查询子问题的解，算法的效率也会大大提高。理论描述太生硬枯燥，直接看例子吧。斐波那契数列斐波那契数列斐波那契数列是一个很神奇的数列，是由意大利数学家莱昂纳多·斐波那契提出的，其特点是数列中某一项的值是前两项的和，也可以称为黄金分割数列.LeonardoFibonacci我们可以用下面的通项公式来表示斐波那契数列。从斐波那契数列的公式可知，数列的第n（n>2）项的值f(n)等于f(n)+f(n-1)。如果要得到f(n)的值，需要先求出f(n-1)和f(n-2)的值。为了分析方便，我们假设n=6，我们可以按照下图进行分解，一步步分解成小值。Fibonacci看着上图，想必大家已经想到了程序的实现。我们可以通过递归的方法直接计算出n项的价值。该程序非常简单，如下所示。intfib(intn){if(n==1||n==2)return1;returnfib(n-1)+fib(n-2);}但是很明显这个算法是指数时间复杂度O(2^n)，它的复杂度会随着n的增加呈指数增长，当n取到一定大小时，需要很长时间，显然这不是最优算法。但是，如果我们仔细观察上图中的分解项，就会发现图中有很多重复的子项，这就是上述递归算法复杂度高的原因。那么，它还能优化吗？答案是肯定的。我们可以通过动态规划的思想对上面的算法进行优化。为了避免大量的重复计算，我们可以从最底层的子问题开始计算，将这些子问题的值通过一个表存储起来。当再次遇到这个值时不需要重新计算。如下面的程序，我们从最小的子问题n=1,2开始向上计算，定义一个vector容器来存放计算出的子问题的值，下次直接调用该容器我们计算大问题值。intfib(intn){vector
