动态规划（英语：Dynamic Programming，简称DP）是运筹学的一个分支，是通过把原问题分解为相对简单的子问题的方式求解复杂问题的一种方法。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划[1] 。
这里Programming不是编程的意思，而是决策。但这种决策不是一下就出来的，而是一步步多阶段(multistage)积累出来的。换句话说，我们需要一个决策，但这个决策太大了，我们做不了，所以需要把它递归到我们可以简单做出决策的状态，然后从这些状态开始，慢慢的“动态地”演进到最终的决策。
把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。在多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化的过程为动态规划方法。
动态规划没有统一的处理方法，必须根据问题的各种性质并结合一定的技巧来处理。动态规划问题一直是大厂面试时最频繁出现的算法题，主要原因在于此类问题灵活度高，思维难度大，没有很明显的套路做法。没有放之四海皆准的计算动态规划解决方案的公式。
动态规划算法是国际大学生程序设计竞赛（ACM）用得最多的算法之一，深入学习动态规划很重要。
二、基本思想动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。
动态规划算法的核心是记住已经求过的解，记住求解的方式有两种：
①通过具有记忆功能的迭代自顶而下求解;
②一般采用迭代法通过自底而上求解。
动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为它可以用空间换取时间，特别是规模比较大时，大幅减少搜索与计算的时间。
三、动态规划分类动态规划一般可分为四类：
- 线性动态规划
例如：拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等；
- 区域动态规划
例如：石子合并, 加分二叉树,统计单词个数,炮兵布阵等；
- 树形动态规划
例如：皇宫守卫,贪吃的九头龙,二分查找树,聚会的欢乐,数字三角形等；
- 背包动态规划
例如：01背包问题,完全背包问题,分组背包问题,装箱问题,挤牛奶等。
四、适用条件能采用动态规划求解的问题，通常要具备3个性质：
(1) 问题中的状态必须满足最优化原理最优化原理的定义：作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的诸决策必构成最优决策。简而言之，一个最优化策略的子策略总是最优的。
最优化原理用数学语言描述：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 < k < n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk 1，Dk 2，…，Dn也是最优的。
最优化原理是动态规划的基础。任何一个问题，如果失去了这个最优化原理的支持，就不可能用动态规划方法计算。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构是指原问题的最优解包含子问题的最优解。证明见附录1。
(2) 问题中的状态必须满足无后效性所谓的无后效性是指，下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结。
(3) 子问题重叠性子问题重叠性即子问题之间是不独立的，一个子问题在下一阶段决策中可能被屡次使用到。
动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
子问题重叠不是使用动态规划的必要条件，但是问题存在子问题重叠的特性更能够充分彰显动态规划的优势。若是没有这条性质，动态规划算法同其它算法相比就不具有优点。
五、动态规划解题思路1、解题步骤1) 划分阶段按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段必定要是有序的或者是可排序的，不然问题就没法求解。
2) 确定状态和状态变量将问题发展到各个阶段时所处于的各类客观状况用不一样的状态表示出来。
DP状态的确定主要有两大原则：
- 最优子结构
- 无后效性
例如：图5-1求得一条从A到G的最短路径？
图5-1
可以用Dijkstra算法求得， Dijkstra算法符合动态规划的这一特性：待求解的问题分解为若干个子问题，前一子问题的解，为后一子问题的求解提供了有用的信息。动态规划主要是解决多阶段决策问题，并且阶段间存在着相互影响。该例子有7个阶段，初始阶段状态为A, 第2阶段状态有两个{B1，B2}, 第三阶段状态有4个{C1,C2,C3,C4}，等等。一个阶段可以有多个状态。
3) 确定决策并写出状态转移方程由于决策和状态转移有着自然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。因此若是确定了决策，状态转移方程也就可写出。
我们只需要用分类讨论的思想来枚举所有小状态向大状态转移的可能性即可推出DP转移方程。
4) 初始条件和边界状况给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。即设置初始值，考虑边界状况。
2、动态规划决策过程示意图
图5-2
六、应用动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果 。
例子1 0-1背包问题现有n件物品和一个容量为c的背包。第i件物品的重量是重量为w[i]，价值是v[i]。已知对于一件物品必须选择取（用1表示）或者不取（用0表示），且每件物品只能被取一次（这就是“0-1”的含义）。求放置哪些物品进背包，可使这些物品的重量总和不超过背包容量，且价值总和最大。
1> 穷举法有两种方法：第一种方法，计算从n件物品中，取任意数量的物品有多少种取法？利用高中的排列组合知识，分类取：
取0个物品，有1种取法；
取1个物品，有n种取法；
取2个物品，有n*(n-1)/2种取法；
...
取n个物品，有1种取法；
总共的取法为：
共有2ⁿ种取法，然后分别计算2ⁿ种取法的物品的总重量和总价值，选出其中满足条件（物品的重量总和不超过背包容量，且价值总和最大）的一种取法。
第二种方法，将n个物品排成一行，对于一件物品必须选择取（用1表示）或者不取（用0表示），想象成n个0、1组成的序列，如00010...010；
01100...100;
10001...110;
...
利用高中的排列组合知识, 这样的序列有2*2*2*2...*2 = 2^n种。
0-1背包问题中的“0-1”就是这个意思。
每一个序列代表一种取法，选出其中满足条件（物品的重量总和不超过背包容量，且价值总和最大）的一种取法。
显然，穷举法的运行时间是O(2ⁿ)，当n很大时真的是慢如蜗牛。
2、回溯法用回溯法实现就是要在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。具体方法如下：
①对每一个物品i，对该物品只有选与不选两种决策，有n个物品，可以形成一棵 深度为n的决策树；
②遍历这棵树，以枚举所有情况，最后进行判断，若重量不超过背包容量，且总价值最大，该方案就是最优的。
假设你是一个小偷，背着一个可装下6磅东西的背包，你可以偷窃的商品如下：
