动态规划
算法思想
dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.——维基百科
动态规划的思想：将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存下来，即空间换时间。
算法本质
动态规划的本质（核心），是对问题状态的定义和状态转移方程的定义，也可以用非数学的话来描述：原问题的解如何由子问题的解组合而成。
考察一个实际问题：
斐波那契数列：1、1、2、3、5、8、13、21、34、……
数学定义：F(0)=1,F(1)=1,F(2)=2,……, F(n)=F(n-1)+F(n-2)
上述的F(n)就是一个子问题，也就可以叫做状态，定义”F(n)为斐波那契数列的第n个数“，就叫做状态的定义。
而对于数学方程F(n)=F(n-1)+F(n-2)，可以理解为从状态F(n-1)和F(n-2)转移到状态F(n)，而这样的方程的定义就叫做状态转移方程的定义。
在对状态和状态转移方程的定义过程中，满足“最优子结构”是一个隐含的条件（否则根本定义不出来）。
适用的情况
能采用动态规划求解的问题的一般要具有3个性质：
（1）最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。
（2）无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
（3）有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
算法步骤
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。
初始状态→│决策１│→│决策２│→…→│决策ｎ│→结束状态
动态规划的设计都有着一定的模式，一般要经历以下几个步骤：
（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
（2）确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
（3）确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
（4）寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。
实际应用中可以按以下几个简化的步骤进行设计：
（1）分析最优解的性质，并刻画其结构特征。
（2）递归的定义最优解。
（3）以自底向上或自顶向下的记忆化方式（缓存）计算出最优值。
（4）根据计算最优值时得到的信息，构造问题的最优解。
动态规划与分治算法、贪心算法的区别
（1）动态规划与分治算法
分治算法的思想也是将问题划分成若干个相互独立的子问题，先解决子问题，然后合并其结果就得到原问题的解。与此不同，动态规划适用于子问题独立且重叠的情况，也就是各子问题包含公共的子子问题。
对于具有很多重叠子问题的问题，若用分治算法则会做许多不必要的工作，即重复地求解公共的子问题。动态规划对每个子子问题只求解一次，将其结果保存在一张表中，从而避免每次遇到各个子问题时重新计算答案。
《算法导论》： 动态规划要求其子问题既要独立又要重叠，这看上去似乎有些奇怪。虽然这两点要求听起来可能矛盾的，但它们描述了两种不同的概念，而不是同一个问题的两个方面。如果同一个问题的两个子问题不共享资源，则它们就是独立的。对两个子问题俩说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，是重叠的，则它们是重叠的。
（2）动态规划与贪心算法
贪心算法也是将问题分解成若干个子问题，通过每个子问题的最优解得到后一个子问题的最优解，通过局部最优解产生全局最优解，对于大多数问题，贪心算法能产生最优解，但不是全部（比如最大最小值问题）。
同样，贪心算法使用的也是最优化问题，具有最优子结构。但是贪心算法不同于动态规划，每一步求解得到一个最优解，通过这个最优解推到下一步的最优解，而上一部之前的最优解则不作保留，每一步都能是选择最优解，最终得到问题的解。
动态规划的全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 。
《算法之道》：
摘自知乎：
一个问题是该用递推、贪心、搜索还是动态规划，完全是由这个问题本身阶段间状态的转移方式决定的！
每个阶段只有一个状态–>递推；
每个阶段的最优状态都是由上一个阶段的最优状态得到的–>贪心；
每个阶段的最优状态是由之前所有阶段的状态的组合得到的–>搜索；
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的–>动态规划。
|每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到
——这个性质叫做最优子结构；
|而不管之前这个状态是如何得到的
——这个性质叫做无后效性。