递推与动态规划最终
以下为《递推与动态规划最终》的无排版文字预览，完整内容请下载
动 态 规 划讲解：ykw递推?斐波那契数列问：一般而言，不缺草吃的小兔子在出生两个月后就有繁殖能力，且一对兔子每个月能生出一对小兔子来。这里，我们假设兔子还是长生不老的。你一旦得到了一对小兔子，那么在一年之后你最多可以得到多少只兔子？斐波那契数列问：一般而言，不缺草吃的小兔子在出生两个月后就有繁殖能力，且一对兔子每个月能生出一对小兔子来。这里，我们假设兔子还是长生不老的。你一旦得到了一对小兔子，那么在一年之后你最多可以得到多少只兔子？
解：设 ??(??) 为第 ?? 个月兔子的总对数。
我们有：??(??)=上一个月活下来的兔子对数 + 新出生的小兔子数，即 ??(???1)+??(???2)，初始状态为 ??(0)=??(1)=1。斐波那契数列问：求用 1×2 的骨牌铺满大小为 2×?? 的方格的方案总数。斐波那契数列问：求用 1×2 的骨牌铺满大小为 2×?? 的方格的方案总数。
解：设 ??(??) 表示对于 ?? 的铺骨牌方案数。
首先，可以知道 ??(0) = 1.
??(1) 的状态只能通过竖着摆放的一个骨牌得到，因此 ??(1) = 1.
考虑最右面的骨牌，可能是两个骨牌横着摆放，也可能最右面的骨牌单独竖着摆放。因此，有 ??(??) = ??(???1) + ??(???2).平面分割问题 ①问：?? 条直线最多能把平面分成多少区域 ?平面分割问题 ①问：?? 条直线最多能把平面分成多少区域 ?
解：设 ??(??) 为 ?? 条直线把平面分割成的区域个数，分析问题中每增加一条直线时，平面增加了多少区域。画图可知，每增加一条直线，新增加的平面数为新增加的直线被分成的段某某。
递推式： ??(??)=??(???1)+??= ??×(??+1) 2 +1.小学奥数问题问：在二维平面上，从原点 (0,0) 出发，每次只能向下或向右走一个单位，走到 (??,??) 的最短路径数量。小学奥数问题问：在二维平面上，从原点 (0,0) 出发，每次只能向下或向右走一个单位，走到 (??,??) 的最短路径数量。
解：
??[1][??] = ??[??][1] = 1 ?? ?? ?? = ?? ???1 ?? + ?? ?? ???1 , ??,??>1
组合数？小学奥数问题问：在二维平面上，从原点 (0,0) 出发，每次只能向下或向右走一个单位，走到 (??,??) 的最短路径数量。
解：相当于有 ?? 次向下的机会和 ?? 次向右走的机会，方案数为
2?? ?? C2nn动态规划入门?INTRO这篇课件用于DP入门。
前置技能：小学数学知识
约定几个英文缩写：
e.g. 例如 动物都是生物，e.g. 猫是生物。
etc. 等等 动物中有猫，狗，etc.
P.S. 备注 P.S. 这篇课件之后的内容很多是rxz做的。硬币问题您有无限多的硬币，硬币的面值为 1,5,10,50,100,500.
给定一个数额 ??，问您最少用多少枚硬币可以凑出 ??.硬币问题依据生活经验，我们可以采用这种策略：
先尽量用500的，然后尽量用100的……以此类推。
e.g. 666 = 1*500+1*100+1*50+1*10+1*5+1*1,共用10枚硬币。
这就是贪心了。
我们每次使用一个硬币，总能最大程度地解决问题（把剩下要凑的数额变小）。可是，贪心是一种只考虑眼前情况的策略。尽管这一套硬币面值可以采用贪心策略，但是迟早要栽跟头的。硬币问题我们考虑一组新的硬币面值：1,5,11.
于是有了一个反例：如果我们要凑出15，贪心策略是：
15 = 11+4*1，共用 5 枚硬币。
而最佳策略是：
15 = 3*5，共用3枚硬币。硬币问题贪心策略自此陷入困境：鼠目寸光。
在 w=15 时，贪心策略选择了面值 11 的硬币（因为这样可以尽可能降低要凑的数额）。
在选择了面值为 11 的硬币之后，我们只好面对 w=4 的处境。硬币问题我们重新分析刚刚的情况：
w=15时，我们取了11，接下来面对w=4的情况。
w=15时，如果我们取5，接下来就面对w=10的情况。
我们记“凑出??需要用到的最少硬币数量”为 ??(??).硬币问题那么，如果我们取了 11，则：
cost=?? 4 +1=4+1=5.
解释：我们用了一枚面值为 11 的硬币，所以加一；
接下来面对的是 w=4 的情况。??(4) 我告诉你等于4.
相应地，如果我们选择取 5，则：
cost=?? 10 +1=2+1=3.硬币问题那么，w=15时，我们选哪枚硬币呢？
cost最低的那一个！
11： cost=?? 4 +1=4+1=5.
5: cost=?? 10 +1=2+1=3.
1: cost=?? 14 +1=4+1=5.
选择5，?? 15 =3,即为答案！硬币问题我们注意到了一个很棒的性质：
??(??) 只与 ?? ???1 ,?? ???5 ,??(???11) 相关。
更确切地说：
?? ?? =min?{?? ???1 ,?? ???5 ,?? ???11 }+1硬币问题硬币问题这个做法和贪心的区别是：
这个算法对给定的w，会算出取1、5、11的代价，从而确定最终答案。
而贪心直接选择可选的最大硬币，一条路走到黑。硬币问题这个算法的时间复杂度显然是?? ?? .为什么比暴力要快呢？
我们暴力枚举了“使用的硬币”，然而这属于冗余信息。
我们要的是答案，根本不关心这个答案是怎么凑出来的。
要求出??(15)，只需要知道?? 14 ,?? 10 ,??(4)的值。
其他信息不需要。硬币问题可见，我们的做法比暴力快，是因为我们舍弃了冗余信息。
我们只记录了对解决问题有帮助的信息——??(??).
我们能这样干，取决于问题的性质：
求出??(??)，只需要知道几个更小的??(??).
我们将求解??(??)称作求解??(??)的“子问题”。动态规划这就是动态规划（DP, dynamic programming）.
将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。动态规划一旦??(??)确定，“我们如何凑出??(??)”就再也用不着了。
要求出??(15)，只需要知道?? 14 ,?? 10 ,??(4)的值，而?? 14 ,?? 10 ,??(4)是如何算出来的，对之后的问题没有影响。
“未来与过去无关”，这就是无后效性。
P.S. 其严格定义：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。动态规划回顾我们对??(??)的定义：
我们记“凑出??需要用到的最少硬币数量”为??(??).
??(??)的定义就已经蕴含了“最优”。
利用w=14,10,4的最优解，我们即可算出w=15的最优解。
大问题的最优解可以由小问题的最优解推出，这个性质叫做“最优子结构性质”。动态规划什么情况下我们能使用DP呢？
我们能将大问题拆成几个小问题，且满足
无后效性
最优子结构性质动态规划给出一个数字三角形，从其中一个位置只能走到其正下方和右下方两个位置。现在你在三角形的左上角，请找出一条走向最后一行的路径使得这条路径经过的数字之和最大。输出这条路径经过数字的和。7
3 8
8 1 0
2 7 4 4
4 5 2 6 5动态规划设 ?? ??,?? 表示从左上角走到 (??,??) 经过的数字之和的最大值。由于 (??,??) 可以由 (???1,??)、(???1,???1) 两个位置到达，可以列出来式子：
??(??,??)=max? ?? ???1,?? ,?? ???1,???1 +??(??,??).
用一些阶段的状态求得另外一个阶段的状态的过程叫做状态转移，其转移式称为状态转移方程。7
3 8
8 1 0
2 7 4 4
4 5 2 6 57
10 15
18 16 15
20 25 20 19
24 30 27 26 24状态转移动态规划7
3 8
8 1 0
2 7 4 4
4 5 2 6 57
10 15
18 16 15
20 25 20 19
24 30 27 26 24状态转移动态规划练习时间：
P1095 守望者的逃离(简单递推1)10min
P1586 四方定理(简单递推2) 10min
P3842 [TJOI2007]线段(简单递推3，选做)状态转移最长上升子序列最长上升子序列（LCS）问题：
给定长度为??的序列??，从??中抽取出一个子序列，这个子序列需要单调递增。问最长的上升子序列（LCS）的长度。
e.g. 1,5,3,4,6,9,7,8：LCS长度为6。最长上升子序列我们记?? ?? 为以 ?? ?? 结尾的LCS长度，那么答案就是max{?? ?? }.
那么，大问题??(??)如何拆成小问题呢？考虑比??小的每一个??：
如果 ?? ?? > ?? ?? ，那么?? ?? 可以取?? ?? +??.
解释：我们把 ?? ?? 接在 ?? ?? 的后面，肯定能构造一个以 ?? ?? 结尾的上升子序列，长度比以 ?? ?? 结尾的LCS大1.最长上升子序列那么，我们可以写出状态转移方程了：
?? ?? = max ??请点击下方选择您需要的文档下载。
- 月考国旗下教师节讲话
- 教案大班科学：有趣的影子
- 中班语言领域活动:《猜猜我有多爱你》教学反思
- 十只兔子去野餐-1
- 十只兔子去野餐-1
- 24 教学设计 音乐活动《小兔跳跳跳》冯某某
- 3.我的游戏活动反思方案
- 教师数学加油站11.20答案
- 儿童剧《小兔乖乖》剧本
- 耷拉耳朵的小兔教学反思
- 耷拉耳朵的小兔教案
- 《逃家小兔》阅读教学设计
- 《猜猜我有多爱你》练习题
- 龟兔赛跑教学设计
- 信息技术化教学课件
- 蘑菇房子ppt课件
- 孙红娜教学设计与反思
- 教学设计和反思
- 耷拉耳朵的小兔教学反思
- 小二班体育教案-兔子跳
以上为《递推与动态规划最终》的无排版文字预览，完整内容请下载
递推与动态规划最终由用户“zmscchu”分享发布，转载请注明出处