提升:从枚举、进阶,到动态规划(Dynamic Programming)

作者/分享人:zglg
向 Ta 提问
工作 5 年多,前软件工程师,现算法工程师,Pandas 开源库贡献者。为人厚道,做事严谨,个人公众号 id : alg-channel

枚举,一般容易想到,但不是高效的算法,怎么办?动态规划(DP)通常可以拿来做优化。

本次 Chat 我们 Talk:如何通过3个难度依次增大的实例,一步一步接近 DP,主要内容包括:

  1. 通过最通俗易懂的例子:Climbing Stairs (爬楼梯),初步领悟 DP,带有详细的分析思路和代码。代码版本一步一步从1.0,优化到1.1,最后形成终极版1.2.
  2. 聊一道面试真题,分析机器人行驶最短路径,再次体会 DP 构思过程;
  3. 通过2个例子,总结使用 DP 的通用条件;
  4. 实战 LeetCode 上的一道题:Longest Valid Parentheses (最长连续有效括号对),一次通过率是23.4%,属于 hard 级别。这道题有难度,但具有很强的 DP 风格,是理解 DP 的试金石;
  5. 使用 Python 编码实现以上3个问题;
  6. 最后梳理 DP,通过以上,您将学习到 DP 求解最重要的两个步骤:
    • 如何自顶而下地思考方式找到 DP 的迭代方程?
    • 通过自底向上地方法将子问题求解写入到临时表中,这样保证只做一次求解。
已有917人预订
预订达标
文章出炉
交流日期
     
18.06.11
18.06.20
18.06.25 20:30
查看文章评论/提问
Hee
最后推荐的书英文版的,还没毕业呢,看得懂千分之一算不错了,好吧,已经哭了
zglg: 今晚chat,我还会推荐一本中文算法书,并提供下载链接。
你可能还喜欢
解读《阿里巴巴 Java 开发手册》背后的思考
Hollis
初探 Kafka
阿福
LeetCode 刷题指南以及常见算法题解题思路总结
kerry
大数据开发面试指南
王知无
高并发系统缓存实战入门
饿了么物流技术团队
7 天从 Java 工程师转型为 Go 工程师
DIU哥
微信扫描登录
关注提示×
扫码关注公众号,获得 Chat 最新进展通知!