江苏龙网

  1. 主页 > 生活百科 > >

详细解释，从入门到实践，逐步讲解 经典中的经典算法，动态规划( 二 )

动态规划


动规解题的一般思路(标准官方,不过经过前边讲解应该就能理解了):
将原问题分解为子问题(开头已经介绍了怎么分解)
(注意:1,子问题与原问题形式相同或类似,只是问题规模变小了,从而变简单了;
2,子问题一旦求出就要保存下来,保证每个子问题只求解一遍)
确定状态(状态:在动规解题中,我们将和子问题相关的各个变量的一组取值,称之为一个"状态",一个状态对应一个或多个子问题所谓的在某个状态的值,这个就是状态所对应的子问题的解,所有状态的集合称为"状态空间".我的理解就是状态就是某个问题某组变量,状态空间就是该问题的所有组变量) 另外:整个问题的时间复杂度就是状态数目乘以每个状态所需要的时间
确定一些初始状态(边界条件)的值 (这个视情况而定,千万别以为就是最简单的那个子问题解,上面只是例子,真正实践动规千变万化)
确定状态转移方程 (这一步和第三步是最关键的 记住"人人为我"递推,由已知推未知)
适合使用动规求解的问题:
1,问题具有最优子结构
2,无后效性 说的花里胡哨的,其实一般遇到求最优解问题一般适合使用动态规划




推荐阅读


上一篇：蒙顶黄芽是什么茶,蒙顶黄芽的功效是什么

下一篇：泡茶有什么讲究,茶席的席面设计有讲究