动态规划DP算法详解

1.简介

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

动态规划也是学习算法的同学最为头疼的一个重要算法，其类型宽泛让人无从下手，又极其的烧脑很难理解，事实上，动态规划是算法学习者的一个重要的门槛，也是一个瓶颈，掌握方法很重要，本节虽然不提供任何的具体代码，但希望简介以及介绍曲线的方式让读者能够更好的掌握。

2.思想

动态规划的基本思想是：问题的最优解如果可以由子问题的最优解推导得到，则可以先求解子问题的最优解，在构造原问题的最优解；若子问题有较多的重复出现，则可以自底向上从最终子问题向原问题逐步求解。

比如说著名的斐波那契定理a[i]=a[i-1]+a[i-2]，就是一个特别好的理解方式，为什么直接写公式的算法（自底向上，从1开始递增）效率就是比递归（自顶向下，从n开始向下）的要好？

让我们来熟悉一下动态规划的特点：

a) 把原始问题划分成一系列子问题；

b) 求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间

c) 自底向上地计算。

d) 整体问题最优解取决于子问题的最优解（状态转移方程）（将子问题称为状态，最终状态的求解归结为其他状态的求解）

很简单，因为递归的方式return f(n-1)+f(n-2)会产生一些重复计算，当计算f(5)+f(4)中，f(5)其实又包含了一次f(4)，而动态规划的出现，就是为了减少这样的重复计算，通过确认一个个的状态以及到达下一个状态的【状态转移方程】，来表现，一般而言，我们使用数学语言直接表示【状态转移方程】。

3. 分类

动态规划可以分为如下四大类，可以依次进行学习：

线性动规，区域动规，树形动规，背包动规。

4. 学习方法

一切的开始，都必须要勤记笔记，在最初的学习中，比如最大不下降子序列这题目，我们可以更具题意将题目要求，总结题目意思，发现是否选取这个序列数是一个状态，这个状态分为两种情况：选取，不选取，我们可以在草稿纸上面讲每一个状态利用一个二叉树画出来，然后推到出正确的方案，这是第一步，接着我们讲二叉树中的每一个数据提出，尝试着利用动态规划的思维，将这课树的状态转移方程提出，最后根据这个状态转移方程，写出最终的答案。

在熟悉相关类型的题目达到一定的程度的时候，自然得心应手。

5. 相关例题

可以直接从dotcpp网站标签中搜索动态规划即可，动态规划拥有海量的题目，非常适合深入理解和练习。