首页
技术小册
AIGC
面试刷题
技术文章
MAGENTO
云计算
视频课程
源码下载
PDF书籍
「涨薪秘籍」
登录
注册
动态规划算法导读
最大连续乘积子串
字符串编辑距离
格子取数问题
交替字符串
最长递增子序列
海量数据处理算法导读
关联式容器
分而治之
外排序
分布式处理之MapReduce
多层划分
Bitmap
Bloom Filter
Trie树(字典树)
倒排索引
语言基础
概率统计
智力逻辑
系统设计
操作系统
40亿个数中快速查找
后缀树
倒排索引的编码与实践
随机取出其中之一元素
最小操作数
最长公共子序列
hash表算法
当前位置:
首页>>
技术小册>>
编程之道-算法面试(下)
小册名称:编程之道-算法面试(下)
学习一个算法,可分为3个步骤:首先了解算法本身解决什么问题,然后学习它的解决策略,最后了解某些相似算法之间的联系。例如图算法中, 广搜是一层一层往外遍历,寻找最短路径,其策略是采取队列的方法。 最小生成树是最小代价连接所有点,其策略是贪心,比如Prim的策略是贪心+权重队列。 Dijkstra是寻找单源最短路径,其策略是贪心+非负权重队列。 Floyd是多结点对的最短路径,其策略是动态规划。 而贪心和动态规划是有联系的,贪心是“最优子结构+局部最优”,动态规划是“最优独立重叠子结构+全局最优”。一句话理解动态规划,则是枚举所有状态,然后剪枝,寻找最优状态,同时将每一次求解子问题的结果保存在一张“表格”中,以后再遇到重叠的子问题,从表格中保存的状态中查找(俗称记忆化搜索)。
下一篇:
最大连续乘积子串
该分类下的相关小册推荐:
算法面试通关 50 讲
数据结构与算法(上)
数据结构与算法(中)
业务开发实用算法精讲
数据结构与算法之美
编程之道-算法面试(上)
数据结构与算法(下)