分享近期学习的内容：动态规划法

kgrffin

动态规划法                                明确求最优解            
                 
（一）概念                 
                 
动态规划法用于求解具有最优子结构的多阶段决策活动的最优解，将原问题分解成若干子问题，列出并保存各种可能的子问题解，找到子问题的最优解，从而构造原问题的最优解。                 
                 
必须含有的要素：                 
①最优子结构                ：原问题的最优解所包含的子问题的解也是最优的，利用已解决过的子问题的最优解来求解原问题的最优解，可使用                                                                                        ②递归        或循环解决问题。   
无后效性：过程的发展仅与此阶段的状态有关，与此阶段前的阶段所经历过的状态无关。                 
                 
多阶段决策活动：                 
活动的过程可分为若干个互相联系的阶段，在每个阶段都需作出决策（或采取措施），一个阶段的决策会影响下一阶段的决策，从而完全确定了一个活动的过程的路线。                 
各阶段采取的决策依赖于当前状态，又引起状态的转移。                 
各阶段的决策构成一个决策序列，称为一个策略。每个阶段都有若干个决策可供选择，因而有许多策略供选取。每个策略都可用数量衡量活动效果，策略不同效果不同。                 
                 
将原问题分解成若干子问题的过程自顶向下与自底向上相同，该过程与分治法非常相似。                 
每次问题分解产生的子问题并不总是新问题，有些子问题会被重复计算多次，动态规划法将                                                                        ③子问题的解记录在表格中                        ，每个子问题的解先在表中查找结果，节省大量的重复计算时间。     
                 
（二）时间复杂度                 
                 
1.自顶向下O（2^n）                 
动态规划法自顶向下实现时，                 
规模从n到n-1时，表中没有n-1的解，查表的意义可以忽略不计，因此要继续向下递归，递归到第1层（或第0层）时才有解。                 
设每次分解为2个子问题，解空间形成一个二叉树，n为二叉树的深度，二叉树的每个结点都是一个子问题，都要计算（或查表）1次，共O（2^n）。                 
                 
2.自底向上O（n^a）                 
动态规划法自底向上实现时，                 
第1层（或第0层）有解，中间解查表或计算可得。                 
设每次分解为2个子问题，解空间形成一个二叉树，n为二叉树的叶结点数量，a为二叉树的深度，自底向上合并解空间，每层执行n次循环，循环嵌套a层，时间复杂度O（n^a）。  



以上是学习内容，如有错误或不足，望指正。               

Bullfight2916

有一个问题想请教一下前辈，其实好像很多时候我都理解动态规划的含义，但是就是在做题或者实际应用的时候想不起如何使用，或者是想不到这样的递推式。
比如说上点难度的正则表达式，就好像很难定义动规数组到底是几个维度比较合适，递推关系怎么做。
楼主有这类的经验吗？
感觉很像那种，只会做过的、看明白解析的题。

kgrffin

客气了，我前天才刚学，称不上前辈，分享下心得而已混个发贴数。目前还未学到过这方面。