动规解题的一般思路(标准官方,不过经过前边讲解应该就能理解了):
将原问题分解为子问题(开头已经介绍了怎么分解)
(注意:1,子问题与原问题形式相同或类似,只是问题规模变小了,从而变简单了;
2,子问题一旦求出就要保存下来,保证每个子问题只求解一遍)
确定状态(状态:在动规解题中,我们将和子问题相关的各个变量的一组取值,称之为一个"状态",一个状态对应一个或多个子问题所谓的在某个状态的值,这个就是状态所对应的子问题的解,所有状态的集合称为"状态空间".我的理解就是状态就是某个问题某组变量,状态空间就是该问题的所有组变量) 另外:整个问题的时间复杂度就是状态数目乘以每个状态所需要的时间
确定一些初始状态(边界条件)的值 (这个视情况而定,千万别以为就是最简单的那个子问题解,上面只是例子,真正实践动规千变万化)
确定状态转移方程 (这一步和第三步是最关键的 记住"人人为我"递推,由已知推未知)
适合使用动规求解的问题:
1,问题具有最优子结构
2,无后效性 说的花里胡哨的,其实一般遇到求最优解问题一般适合使用动态规划
推荐阅读
- MacBook 怎么选，这里有详细介绍
- 从源码层，拆解OracleJDK和OpenJDK有什么区别？
- 从0开始学编程，方法真的对了吗？
- 从养生角度来看，天天洗澡和一周洗一次澡，哪个对健康更有利？
- 黄茶是什么茶,详细介绍黄茶品种君山银针
- 解酒茶那个好赶黄茶怎么样,学茶从泡准杯茶开始
- 华为交换机的基本配置详细说明
- “App 优化网络，先从优化 DNS 开始”
- 网站推广及运营经验分享
- 详细茶道全流程,茶道基础