动态规划（DP）

动态规划（ Dongtai Planning  Dynamic Programming，简称DP）     

多阶段决策过程的最优化问题

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线，这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。如下图所示：

多阶段决策过程，是指这样的一类特殊的活动过程，问题可以按时间顺序分解成若干相互联系的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列。

基本概念      

动态规划是解决 “多阶段决策问题”的一种高效算法。

动态规划是通过合理组合子问题的解从而解决整个问题解的过程。

动态规划是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

即把一个问题转化为若干个形式相同，但规模更小的子问题，从而递归解决整个问题。

其中的子问题并不是独立的，这些子问题又包含有公共的子子问题……

动态规划算法对每个子问题只求一次，并将其结果保存在一张表中(数组)，以后再用到时直接从表中拿过来使用，避免重复计算相同的子问题。
“不做无用功”的求解模式，大大提高了程序的效率。

如何拆分问题，才是动态规划的核心。
而拆分问题，靠的就是状态的定义和状态转移方程的定义。

真正含义

在一个困难的嵌套决策链中，决策出最优解。

本质

对问题状态的定义和状态转移方程的定义。

状态转移的实质

决策

动态规划的基本概念和基本模型构成

阶段、状态 、决策、策略 、状态转移方程

阶段和阶段变量
用动态规划求解一个问题时，需要将所给问题的全过程恰当地分成若干个相互联系的阶段，以便按一定的次序去求解。

过程不同，阶段数就可能不同。

描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k表示。
阶段的划分一般是根据时间和空间的自然特征来划分。

阶段的划分要便于把问题转化成多阶段决策问题。

状态和状态变量
某一阶段的出发位置称为状态，通常一个阶段有多个状态。
一般地，状态可以用一个或一组数（变量）来描述，用来描述状态的变量称为状态变量。

决策、决策变量和决策允许集合
一个阶段的状态给定以后，从该阶段的每一个状态出发，通过一次选择性的行动转移至下一阶段的相应状态称为决策。

或者说在对问题的处理中作出的每种选择性的行动就是决策。

一个实际问题可能要有多次决策和多个决策点，在每一个阶段的每一个状态中都需要有一次决策。

决策可以用变量来描述，这种描述决策的变量称为决策变量。
在实际问题中，决策变量的取值往往限制在某一个范围之内，此范围称为允许决策集合。

策略和最优策略

全过程中各阶段决策变量所组成的有序总体称为策略。
所有阶段的决策有序组合构成一个策略。

在实际问题中，最优效果的策略叫最优策略。

状态转移方程
前一阶段的终点就是后一阶段的起点，对前一阶段的状态作出某种决策， 产生后一阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律，称为状态转移方程。

条件

拓扑图（DAG，有向无环图）（可拓扑排序）

最优子结构

即，子问题的最优解是整个问题的最优解的一部分。

无后效性

性质

布尔性

动态规划和递推有些相似（尤其是线性动规），但是不同于递推的是：

递推求出的是数据，所以只是针对数据进行操作；而动态规划求出的是最优状态，所以必然也是针对状态的操作，而状态自然可以出现在最优解中，也可以不出现——这便是决策的特性（布尔性）。

批判性继承思想

状态转移方程可以如此定义：

下一状态最优值=最优比较函数（已经记录的最优值，可以由先前状态得出的最优值）

——即动态规划具有判断性继承思想

可推导性

由于每个状态均可以由之前的状态演变形成，所以动态规划有可推导性。

最优化原理
整个过程的最优策略具有：无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的决策必须构成最优策略的性质。
即，子问题的局部最优将导致整个问题的全局最优。
即，问题具有最优子结构的性质，
也就是说一个问题的最优解只取决于其子问题的最优解，而非最优解对问题的求解没有影响。
无后效性原则
某阶段的状态一旦确定，则此后过程的演变不再受此前各状态及决策的影响。

即每个当前状态会且仅会决策出下一状态，而不直接对未来的所有状态负责，

也就是说，“未来与过去无关”，当前的状态是此前历史的一个完整的总结，此后的历史只能通过当前的状态去影响过程未来的演变。

可以浅显地理解为：

Future  never  has  to  do  with  past  time  ,but  present  does.

现在决定未来，未来与过去无关。

若直接缩小规模而划分出的子问题不满足最优子结构

引入更多用于区分不同子问题的“状态”。

对于不能划分阶段的问题，不能运用动态规划来解；
对于能划分阶段，但不符合最优化原理的，也不能用动态规划来解；
既能划分阶段，又符合最优化原理的，但不具备无后效性原则，不能用动态规划来解。

方式

正推：
从初始状态开始，通过对中间阶段的决策的选择，达到结束状态。我们也称之为递推。
倒推：
从结束状态开始，通过对中间阶段的决策的选择，达到初始状态。我们可以称之为记忆化搜索。

 把大象装进冰箱 写出一个DP需要几步？

划分阶段
确定状态和状态变量

除了“问题的规模”这一直接的状态，还应考虑一些附加的，用来满足“最优子结构”这一性质的额外状态。
确定决策并写出状态转移方程

根据状态的实际意义去转移，一般有两种考虑方式：“如何分解”和“如何合并”，根据实际选择。
寻找边界条件

分析复杂度

时间复杂度=状态总数x单次转移复杂度
编程实现程序（正推或倒推）

注意各类边界，注意数据类型（爆int？double精度？）

优化

削减状态

优化转移

应用

计数类问题（统计方案总数）

最优决策类问题 （最大值或最小值）

记忆化搜索

记忆化搜索=搜索的形式+动态规划的思想。

记忆化搜索的思想是,在搜索过程中，会有很多重复计算,如果我们能记录一些状态的答案，就可以减少重复搜索量 

近似于暴力

线性DP

综合难度在所有动规题里最为简单。

线性动规既是一切动规的基础，同时也可以广泛解决生活中的各项问题——比如在我们所在的三维世界里，四维的时间就是不可逆式线性。

线性动态规划是在线性结构上进行状态转移，这类问题不像背包问题、区间DP等有固定的模板。

线性动态规划的目标函数为特定变量的线性函数，约束是这些变量的线性不等式或等式，目的是求目标函数的最大值或最小值。

例题

子序列问题

LIS (Longest Increasing Subsequence，最长上升子序列)

最长上升子序列的元素不一定相邻

最长上升子序列一定是原序列的子集。

给定n个元素的数列，求最长的上升子序列长度。
这类动态规划问题的状态一般是一维的f[i]，第i个元素的最优值只与前i-1个元素的最优值 （正推）或第i+1个元素之后的最优值 （倒推） 有关。

n^2做法

首先，对于每一个元素来说，其最长上升子序列就是其本身。那我们便可以维护一个dp数组，使得dp[i]表示以第i元素为结尾的最长上升子序列长度，那么对于每一个dp[i]而言，初始值即为1；

那么dp数组怎么求呢？我们可以对于每一个i，枚举在i之前的每一个元素j，然后对于每一个dp[j],如果元素i大于元素j，那么就可以考虑继承，而最优解的得出则是依靠对于每一个继承而来的dp值取max。

 1 for(int i=1;i<=n;i++)
 2     {
 3         dp[i]=1;//初始化 
 4         for(int j=1;j<i;j++)//枚举i之前的每一个j 
 5         if(data[j]<data[i] && dp[i]<dp[j]+1)
 6         /*用if判断是否可以拼凑成上升子序列，
 7           并且判断当前状态是否优于之前枚举
 8           过的所有状态,如果是，则↓*/
 9         dp[i]=dp[j]+1;//更新最优状态 
10         
11     }