内容简介:最优解 依赖重复计算的 独立的 子过程1.发现最优解结构2.推到递归式
动态规划总结
最优解 依赖重复计算的 独立的 子过程
1.发现最优解结构
2.推到递归式
3.自低向上存储子过程结果过(备忘录,非最优子过程,只是存储,类似迷宫)
4.最优解的存储和计算
这里1:
1)子问题发现/定义、假设已经有了最优解,怎么通过子问题解决。比如工厂最快流水线,已经选了一条路径,要知道如何选择的,需要知道除固定节点后前面如何选择的。矩阵乘法,知道划分后,需要知道最外层两个括号分别如何计算。LCS知道最终解后,需要知道除最后一个节点外前面解如何选择的。
2)选择 需要依赖哪些子问题(越少越好,矩阵乘法无法做到只依赖一个,依赖两个。工厂流水和LCS可以选择多个,但是一个很简单直接求取,选择依赖一个);需要选择依赖(矩阵循环所有一对可能选择其1,LCS和工厂选择满足更优的)
3)注意满足重复计算和独立(最长非重复路径这种问题因为一个子问题用的点其他子问题不能用,所以子问题的最优不是独立的,无法用动态规划),需要简单的证明最优子解的选择会导致最优解
4)局部计算(i-k或者0-2)
LCS:
两个串最长非连续公共子串
假设最优解已有去推子问题(固有思维就是对两个串加节点,才是n与n-1的关系,不太一样的思维)
矩阵
矩阵最小乘法次数的组合
同样的,考虑矩阵多一个n,n-1的关系,改思维习惯
生产线
这个虽然可以用加一个节点,但是从最终最优解来推也可以的。
climits的INT_MAX
vector
以上所述就是小编给大家介绍的《算法之动态规划》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
高性能MySQL
施瓦茨 (Baron Schwartz)、扎伊采夫 (Peter Zaitsev)、特卡琴科 (Vadim Tkachenko) / 宁海元、周振兴、彭立勋、翟卫祥,刘辉 / 电子工业出版社 / 2013-5-1 / 128.00元
《高性能mysql(第3版)》是mysql 领域的经典之作,拥有广泛的影响力。第3 版更新了大量的内容,不但涵盖了最新mysql 5.5版本的新特性,也讲述了关于固态盘、高可扩展性设计和云计算环境下的数据库相关的新内容,原有的基准测试和性能优化部分也做了大量的扩展和补充。全书共分为16 章和6 个附录,内容涵盖mysql 架构和历史,基准测试和性能剖析,数据库软硬件性能优化,复制、备份和恢复,高可......一起来看看 《高性能MySQL》 这本书的介绍吧!
Base64 编码/解码
Base64 编码/解码
MD5 加密
MD5 加密工具