文档介绍：动态规划入门
谢逸达
1
自我介绍
爱生活也爱死亡
爱学术也爱妹子
爱游戏也爱算法
今天你看我研究算法
明天我给你发明算法
我不是小受
我是算法哥
限量版算法哥
仅售一封情书(限妹子)
关于本次讲座
个人讲课风格
第一追求:有趣——不折磨受众
第二追求:易懂——让受众能够理解
第三追求:深刻——能引发受众的思考
目录
讲座内容
分治
记忆
动态规划基本概念
递推法解题
动态规划的本质
一些算法小剧场
从分治开始
分而治之为上策
Divide and Conquer –分裂和征服
来源–战国时的合纵连横
分治的两个思想
分解和转化–解决问题的方法
本原–方法的理论保证
问题的分解
如何把大象装入冰箱?
打开冰箱门- 装入大象- 关闭冰箱门
如何挣一亿人民币?
先去挣一块钱–捡、打工、抢小朋友……
然后重复执行你的算法一亿次!
同理:如何刷到OJ题数第一?
两种分解:
分治–把问题分解几个互不相关的子问题
减治–把问题的规模缩小
问题的转化
数学家去当消防队员
消防队长:假设楼房起火,您怎么办?
数学家回答:把消防栓接到软管上,打开水龙头,把火浇灭。
队长:正确!假设楼房没有起火,您怎么办?
数学家思考后回答:把楼房点燃!
为什么?
把新问题转化为一个已经解决过的问题
分解和转化的困境
转化的基本思想:
P:{原问题的所有子问题}(问题分解)
Pi:{i问题及能转化为i问题的问题}(问题转化)
∪pi=P Pi∩Pj=空集(i≠j)
i问题被称为元问题
如果元问题有无穷个?
世间没有两片相同的树叶
本原
人类的信仰——复杂由简单构成
万物源于水–泰勒斯
原子,元素,素数……
真理是简单的
元问题是有限的!
道可道,非常道
不可知论
分治法解题
斐波拉契数列 F(N)=F(N-1)+F(N-2)
元问题的解:F(1)=F(2)=1
如何求解?
把问题转化为求F(N-1)+F(N-2)
问题数量增多?
主要矛盾和次要矛盾
任何问题=元问题的组合!
快速排序、汉诺塔……