《算法图解》第九章动态规划

作者：宋羽翔-ben | 来源：互联网 | 2023-10-14 15:14

第九章动态规划

用表格法进行找最优方案

背包问题的最优方案

出去玩带东西的最优方案

对于字典查词的话，如果输入有误的话，比较俩个单词的相似性，可以用最长公共子串，不同的为零，相同的把左上方的值再加1导入当前的格子里，（为什么要引入最长公共子串呢及接着引出最长公共子序列呢），最长公共子序列，字母不同的话，就选择左边和上边格子里数值大的那个，相同的话，就是选完左边和上边格子里值大的然后再加1

动态规划不能解决的问题是彼此之间有依赖关系的，比如背包问题里，要偷走音箱也必须偷走CD机，这样的话会超重，

9.1背包问题

9.2背包问题FAQ frequently asked question

9.3最长公共子串

9.4小结

9.1背包问题

偷东西的最终决策表格-----大事进行决策的时候也可以用表格法再加上权重

9.2背包问题FAQ

多增加一个物品---照样可以用上述方法继续

行的排练顺序变了有影响吗？---没有

如果增加一个更小的商品，只有0.5磅，那就将表格的刻度画的更细一些，0.5，1，1.5等

可以偷商品的一部分吗？---动态规划没法处理，但是贪婪算法可以处理

2.其他例子，旅行最优化，换了约束条件，从背包的包的承重约束条件转为时间约束（只有俩天假期），但是还是一样的做法，表格

3.背包可能没装满----也就是说动态规划可能得到的不一定是最优解

4.动态规划可以解决把大问题分解为离散的子问题，而不能解决相互有依赖的子问题

9.3最长公共子串

引入个好玩的

想不出来怎么办，使用费曼算法：

把问题写下来

好好思考

把答案写下来

1.最长公共子串

对于一个词典，如果输入一个和原先要输入的单词只有一点点差别，词典怎么进行判断

画表格，不同的为零，相同的把左上方的值再加1导入当前的格子里，结果如下图

2.引入的问题背景是，如果有两个单词算出来的最长公共子串是一样的结果，那要怎么办呢？

比较其最长公共子序列，具体的算法是字母不同的话，就选择左边和上边格子里数值大的那个，相同的话，就是选完左边和上边格子里值大的然后再加1，结果如下

3.动态规划的实际应用

 生物学家根据最长公共序列来确定DNA链的相似性，进而判断度两种动物或疾病有多相似。最长公共序列还被用来寻找多发性硬化症治疗方案。
 你使用过诸如git diff等命令吗？它们指出两个文件的差异，也是使用动态规划实现的。
 前面讨论了字符串的相似程度。编辑距离（levenshtein distance）指出了两个字符串的相似程度，也是使用动态规划计算得到的。编辑距离算法的用途很多，从拼写检查到判断用户上传的资料是否是盗版，都在其中。
 你使用过诸如Microsoft Word等具有断字功能的应用程序吗？它们如何确定在什么地方断字以确保行长一致呢？使用动态规划！

9.4小结

 需要在给定约束条件下优化某种指标时，动态规划很有用。
 问题可分解为离散子问题时，可使用动态规划来解决。
 每种动态规划解决方案都涉及网格。
 单元格中的值通常就是你要优化的值。
 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。
 没有放之四海皆准的计算动态规划解决方案的公式

推荐阅读

usb
[译]技术公司十年经验的职场生涯回顾

本文是一位在技术公司工作十年的职场人士对自己职业生涯的总结回顾。她的职业规划与众不同，令人深思又有趣。其中涉及到的内容有机器学习、创新创业以及引用了女性主义者在TED演讲中的部分讲义。文章表达了对职业生涯的愿望和希望，认为人类有能力不断改善自己。 ... [详细]

蜡笔小新 2023-12-14 11:31:05
java
Android中高级面试必知必会，积累总结

本文介绍了Android中高级面试的必知必会内容，并总结了相关经验。文章指出，如今的Android市场对开发人员的要求更高，需要更专业的人才。同时，文章还给出了针对Android岗位的职责和要求，并提供了简历突出的建议。 ... [详细]

蜡笔小新 2023-12-14 14:53:02
fetch
sklearn数据集库中的常用数据集类型介绍

本文介绍了sklearn数据集库中常用的数据集类型，包括玩具数据集和样本生成器。其中详细介绍了波士顿房价数据集，包含了波士顿506处房屋的13种不同特征以及房屋价格，适用于回归任务。 ... [详细]

蜡笔小新 2023-12-13 17:45:15
java
手机移动端HTML5和JavaScript如何实现视频上传和压缩视频质量？

本文讨论了在手机移动端如何使用HTML5和JavaScript实现视频上传并压缩视频质量，或者降低手机摄像头拍摄质量的问题。作者指出HTML5和JavaScript无法直接压缩视频，只能通过将视频传送到服务器端由后端进行压缩。对于控制相机拍摄质量，只有使用JAVA编写Android客户端才能实现压缩。此外，作者还解释了在交作业时使用zip格式压缩包导致CSS文件和图片音乐丢失的原因，并提供了解决方法。最后，作者还介绍了一个用于处理图片的类，可以实现图片剪裁处理和生成缩略图的功能。 ... [详细]

蜡笔小新 2023-12-12 15:58:44
java
MVC设计模式的介绍和演化过程

本文介绍了MVC设计模式的基本概念和原理，以及在实际项目中的演化过程。通过分离视图、模型和控制器，实现了代码的解耦和重用，提高了项目的可维护性和可扩展性。详细讲解了分离视图、分离模型和分离控制器的具体步骤和规则，以及它们在项目中的应用。同时，还介绍了基础模型的封装和控制器的命名规则。该文章适合对MVC设计模式感兴趣的读者阅读和学习。 ... [详细]

蜡笔小新 2023-12-11 14:58:14
java
如何实现织梦DedeCms全站伪静态

本文介绍了如何通过修改织梦DedeCms源代码来实现全站伪静态，以提高管理和SEO效果。全站伪静态可以避免重复URL的问题，同时通过使用mod_rewrite伪静态模块和.htaccess正则表达式，可以更好地适应搜索引擎的需求。文章还提到了一些相关的技术和工具，如Ubuntu、qt编程、tomcat端口、爬虫、php request根目录等。 ... [详细]

蜡笔小新 2023-12-14 19:45:47
ip
Python高级之网络编程及TCP/IP协议簇的OSI七层模型介绍

本文介绍了Python高级网络编程及TCP/IP协议簇的OSI七层模型。首先简单介绍了七层模型的各层及其封装解封装过程。然后讨论了程序开发中涉及到的网络通信内容，主要包括TCP协议、UDP协议和IPV4协议。最后还介绍了socket编程、聊天socket实现、远程执行命令、上传文件、socketserver及其源码分析等相关内容。 ... [详细]

蜡笔小新 2023-12-14 18:16:27
java
Java序列化对象传给PHP的方法及原理解析

本文介绍了Java序列化对象传给PHP的方法及原理，包括Java对象传递的方式、序列化的方式、PHP中的序列化用法介绍、Java是否能反序列化PHP的数据、Java序列化的原理以及解决Java序列化中的问题。同时还解释了序列化的概念和作用，以及代码执行序列化所需要的权限。最后指出，序列化会将对象实例的所有字段都进行序列化，使得数据能够被表示为实例的序列化数据，但只有能够解释该格式的代码才能够确定数据的内容。 ... [详细]

蜡笔小新 2023-12-14 15:25:15
java
如何限制php数据库链接数和连接超时时间？

本文介绍了如何使用php限制数据库插入的条数并显示每次插入数据库之间的数据数目，以及避免重复提交的方法。同时还介绍了如何限制某一个数据库用户的并发连接数，以及设置数据库的连接数和连接超时时间的方法。最后提供了一些关于浏览器在线用户数和数据库连接数量比例的参考值。 ... [详细]

蜡笔小新 2023-12-14 14:06:10
ip
Metasploit攻击渗透实践

本文介绍了Metasploit攻击渗透实践的内容和要求，包括主动攻击、针对浏览器和客户端的攻击，以及成功应用辅助模块的实践过程。其中涉及使用Hydra在不知道密码的情况下攻击metsploit2靶机获取密码，以及攻击浏览器中的tomcat服务的具体步骤。同时还讲解了爆破密码的方法和设置攻击目标主机的相关参数。 ... [详细]

蜡笔小新 2023-12-14 12:14:09
ip
图解redis的持久化存储机制RDB和AOF的原理和优缺点

本文通过图解的方式介绍了redis的持久化存储机制RDB和AOF的原理和优缺点。RDB是将redis内存中的数据保存为快照文件，恢复速度较快但不支持拉链式快照。AOF是将操作日志保存到磁盘，实时存储数据但恢复速度较慢。文章详细分析了两种机制的优缺点，帮助读者更好地理解redis的持久化存储策略。 ... [详细]

蜡笔小新 2023-12-13 20:24:11
ip
解决Cydia数据库错误：could not open file /var/lib/dpkg/status 的方法

本文介绍了解决iOS系统中Cydia数据库错误的方法。通过使用苹果电脑上的Impactor工具和NewTerm软件，以及ifunbox工具和终端命令，可以解决该问题。具体步骤包括下载所需工具、连接手机到电脑、安装NewTerm、下载ifunbox并注册Dropbox账号、下载并解压lib.zip文件、将lib文件夹拖入Books文件夹中，并将lib文件夹拷贝到/var/目录下。以上方法适用于已经越狱且出现Cydia数据库错误的iPhone手机。 ... [详细]

蜡笔小新 2023-12-13 19:02:44
main
添加环境光使正方体显示更真实

本文介绍了如何给正方体添加环境光以使其显示更真实。通过在代码中加入环境光的计算，可以让物体的背光部分不再完全黑色，从而增加物体的真实感。代码中使用了顶点属性、光照颜色、光照方向、环境光等参数来计算物体的漫反射，并将计算结果与顶点颜色相乘得到最终的颜色。通过调整环境光的参数，可以达到不同的光照效果。 ... [详细]

蜡笔小新 2023-12-11 20:36:05
merge
git常用命令及其操作详解

本文详细介绍了git常用命令及其操作方法，包括查看、添加、提交、删除、找回等操作，以及如何重置修改文件、抛弃工作区修改、将工作文件提交到本地暂存区、从版本库中删除文件等。同时还介绍了如何从暂存区恢复到工作文件、恢复最近一次提交过的状态，以及如何合并多个操作等。 ... [详细]

蜡笔小新 2023-12-11 20:28:11
ip
微软的STL容器类实现是否线程安全？

本文讨论了微软的STL容器类是否线程安全。根据MSDN的回答，STL容器类包括vector、deque、list、queue、stack、priority_queue、valarray、map、hash_map、multimap、hash_multimap、set、hash_set、multiset、hash_multiset、basic_string和bitset。对于单个对象来说，多个线程同时读取是安全的。但如果一个线程正在写入一个对象，那么所有的读写操作都需要进行同步。 ... [详细]

蜡笔小新 2023-12-11 11:53:23

宋羽翔-ben

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章