美文网首页
算法图解 (九)

算法图解 (九)

作者: EruDev | 来源:发表于2018-06-10 17:24 被阅读0次

动态规划

动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

背包问题

简单算法, 书中一开始是通过排列组合的方式, 但是速度有些慢, 时间复杂度为 O(n2)

引入动态规划, 将背包问题绘制成表格

[图片上传失败...(image-a29e02-1528622649240)]

音响(3000美元、 4磅)、 笔记本电脑(2000美元、3磅)、 吉他(1500美元、1磅)

最终结果, 将吉他和笔记本电脑放入背包时价值最高, 为 3500 美元
[图片上传失败...(image-65950a-1528622649240)]

最长公共子串

引入一个例子。 假设你管理着网站 dictionary.com。 用户在该
网站输入单词时, 你需要给出其定义。

但用户拼错了, 你必须要猜测他原本要输入的是什么单词。 例如, Alex 想查单词fish, 但不小心输入了hish。 在你的字典中, 根本就没有这样的单词, 但有几个类似的单词。

同样绘制表格, 这其实是求最长公共子串

image

最长公共序列

[图片上传失败...(image-ce6269-1528622649240)]

image

伪代码

if word_a[i] == word_b[j]: # 两个字母相同 
    cell[i][j] = cell[i-1][j-1] + 1
else:  # 两个字母不同
    cell[i][j] = max(cell[i-j][j], cell[i][j-1) 

小结

书上的例子还是比较好理解的, 实际中的那些题目可能就够呛了

最后附上小灰漫解动态规划: https://juejin.im/post/5a29d52cf265da43333e4da7

相关文章

  • 算法图解 (九)

    动态规划 动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经...

  • 《算法图解》note 11 总结

    这是《算法图解》的第十一篇读书笔记,是一篇总结。经过1个月的时间,终于把《算法图解》看完了。个人认为,《算法图解》...

  • 算法图解读书笔记

    date: 2017-9-16 11:11:15title: 算法图解读书笔记 算法图解: http://www....

  • 算法图解 读书笔记

    date: 2017-9-16 11:11:15title: 算法图解读书笔记 算法图解: http://www....

  • 算法学习工具

    算法图解可视化工具

  • 图解LZ77压缩算法

    图解LZ77压缩算法

  • 前端

    买一本算法书看一下算法图解

  • LZW压缩算法

    参考链接:超级简单的数据压缩算法—LZW算法压缩算法——lzw算法实现LZW算法 LZW 压缩算法正确图解

  • 2018-05-10

    算法图解 p28 选择排序

  • 算法图解

    下面是本人在看算法书籍时做的笔记。因为前面的比较基础,就从第五章才开始做的笔记 第五章:散列表 个人理解:概念类似...

网友评论

      本文标题:算法图解 (九)

      本文链接:https://www.haomeiwen.com/subject/blyxeftx.html