动态规划入门理解

今天来好好整理一下动态规划的初步运算。
动态规划的主要思想就是以子问题的最优解，来合成得到总问题的最优解，并且子问题的最优解一定是总问题最优解的一部分，即“全局最优解包含局部最优解”。

先来看一道动态规划最最基础，也最最经典的金字塔问题。

http://ybt.ssoier.cn:8088/problem_show.php?pid=1258

根据上面的题，我们来梳理一下思路。

F1递规

int solve(int i,int j)
{
    int res=i==n?0:max(solve(i+1,j),solve(i+1,j+1));
    return a[i][j]+res;
}

这种做法是正确的，but时间效率太低，原因在于重复计算，查找过的点又被再次查找。

F2递推

for(int i=1;i<=n;i++)d[n][j]=a[n][j];
for(int i=n-1;i>=1;i--)
for(int j=1;j<=i;j++)
d[i][j]=a[i][j]+max(d[i+1][j],d[i+1][j+1])

F3来看看记忆化搜索

我们常见的动态规划问题，比如流水线调度问题，矩阵链乘问题等等都是“一步接着一步解决的”，即规模为 i 的问题需要基于规模 i-1 的问题进行最优解选择，通常的递归模式为DP(i)=optimal{DP(i-1)}。而记忆化搜索本质上也是DP思想，当子问题A和子问题B存在子子问题C时，如果子子问题C的最优解已经被求出，那么子问题A或者是B只需要“查表”获得C的解，而不需要再算一遍C。记忆化搜索的DP模式比普通模式要“随意一些”，通常为DP(i)=optimal(DP(j)), j < i。

算法上依然是搜索的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存；一般说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。
记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。

int solve(int i,int j)
{
    if(d[i][j]>=0)return d[i][j];
    d[i][j]=a[i][j]+(i==n?0:max(solve(i+1,j)),solve.(i+1,j+1));
    return d[i][j];
}

动态转移方程

这个动态转移方程，对于初学者和不熟练的同学来说，这个可是做动归题的头痛根源

可以说，只要理出了动态转移方程，那动归题就引刃而解了

所谓的动态转移方程就是一个状态转移到另一个状态的方法

正如动归题的思想——局部最优达到全局最优

那么动态转移方程就是将局部转到全局的利器

正如金字塔的题，当前点的最优解，就是上面两个点最优解更大的值来形成当前最优解

对于动态转移方程，我们既要有大局观念——找出转移的普遍规律

但是，又不能考虑太多，不要去想这其中的一系列转换究竟是如何形成的，因为人脑毕竟是肉做的，不用管怎么一起转换的（特别是递归写的时候，手算很恼火）

动态转移方程所需要的就是一步转移，一个最初值（就是你动归的源点）

希望你能借此大致理解，也可以再看看其他的博客，转移方程对于动归来说至关重要所以务必理解透彻！！！

动态规划基本模型

http://ybt.ssoier.cn:8088/problem_show.php?pid=1286怪盗基德

http://ybt.ssoier.cn:8088/problem_show.php?pid=1285最大上升子序和

http://ybt.ssoier.cn:8088/problem_show.php?pid=1282最大子矩阵

http://ybt.ssoier.cn:8088/problem_show.php?pid=1265最长公共子序列

一.01背包

http://ybt.ssoier.cn:8088/problem_show.php?pid=1267

二.完全背包

http://ybt.ssoier.cn:8088/problem_show.php?pid=1268

三.有个数的01背包

http://ybt.ssoier.cn:8088/problem_show.php?pid=1269

四.混合背包

http://ybt.ssoier.cn:8088/problem_show.php?pid=1270

五.二维价值背包

http://ybt.ssoier.cn:8088/problem_show.php?pid=1271

以上是最基础的动态规划背包问题，可供参考。

动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。
举例：
线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
区域动规：石子合并， 加分二叉树，统计单词个数，炮兵布阵等；
树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶（同济ACM第1132题）等
 这些都是今后要学习的重点，都是动态规划的经典类型，所以未来的路还长。