内容简介：最优解 依赖重复计算的 独立的 子过程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
以上所述就是小编给大家介绍的《算法之动态规划》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Kotlin实战
【美】Dmitry Jemerov（德米特里·詹莫瑞福）、【美】 Svetlana Isakova（斯维特拉娜·伊凡诺沃） / 覃宇、罗丽、李思阳、蒋扬海 / 电子工业出版社 / 2017-8 / 89.00
《Kotlin 实战》将从语言的基本特性开始，逐渐覆盖其更多的高级特性，尤其注重讲解如何将 Koltin 集成到已有 Java 工程实践及其背后的原理。本书分为两个部分。第一部分讲解如何开始使用 Kotlin 现有的库和API，包括基本语法、扩展函数和扩展属性、数据类和伴生对象、lambda 表达式，以及数据类型系统（着重讲解了可空性和集合的概念）。第二部分教你如何使用 Kotlin 构建自己的 ......一起来看看 《Kotlin实战》 这本书的介绍吧!
