动态规划
动态规划
对动态规划,做个总结,我们从一个例子开始:
有一座高度是10级台阶的楼梯,从下往上走,每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
比如,每次走1级台阶,一共走10步,这是其中一种走法。我们可以简写成 1,1,1,1,1,1,1,1,1,1。
再比如,每次走2级台阶,一共走5步,这是另一种走法。我们可以简写成 2,2,2,2,2。
当然,除此之外,还有很多很多种走法。
这里就要用到了动态规划的思想了:动态规划(Dynamic Programming)是一种分阶段求解决策问题的数学思想。
总结起来就是一句话,大事化小,小事化了。
我们用动态规划问题来看看上述的问题吧:
问题建模:
假如只差一步就能走完整个楼梯,要分为几种情况?因为每一步能走一级或者两级台阶,所以有如下两种情况:
1.最后一步走2级台阶,也就是从8级到10级
2.最后一步走1级台阶,也就是从9级到10级
那么在上面的基础上假设1级到8级有X种走法,1级到9级有Y种走法,那么1级到10级有几种走法?
实际上,10级台阶的所有走法可以根据最后一步的不同分为两个部分。
第一部分:最后一步从9级到10级,这种走法的数量和1级到9级的数量一致,也就是Y种。
第二部分:最后一步从8级到10级,这种走法的数量和1级到8级的数量一致,也就是X种。
总的走法就是两种走法的总和,也就是SUM=X+Y种。
我们把10级台阶的走法表达为F(10)此时:
F(10) = F(9)+F(8)
F(9) = F(8)+F(7)
F(8) = F(7)+F(6)
...
F(3) = F(2)+F(1)
看到没,我们把一个复杂的问题分阶段分步的简化,简化成简单的问题,这就是动态规划的思想。
当只有1级台阶和2级台阶时走法很明显,即F(1)=1、F(2)=2,可以归纳出如下公式:
F(n) = F(n-1) + F(n-2)(n >= 3);
F(2) = 2;
F(1) = 1;
动态规划中包含三个重要的概念,最优子结构、边界、状态转移公式。
上面我们分析出F(10)=F(9)+F(8), 其中,F(9)和F(8)是F(10)的最优子结构。
当只有1级和2级台阶时,我们可以直接得出结果,而无需再次简化。我们称F(2)和F(1)是问题的"边界",如果一个问题没有边界,那么这个问题就没有有限解。
F(n) = F(n-1) + F(n-2)是阶段之间的状态转移公式,它是动态规划的核心,决定了问题的每个阶段和下阶段之间的关系。
至此,动态规划的“问题建模就完成了”。
求解问题:
相关文章
- 最少拦截系统 1257 (动态规划)
- 怎么样才能在手机上设置时间规划进行自律?
- Java实现 LeetCode 887 鸡蛋掉落(动态规划,谷歌面试题,蓝桥杯真题)
- Java实现 LeetCode 718 最长重复子数组(动态规划)
- Java实现 LeetCode 1162 地图分析(可以暴力或者动态规划的BFS)
- Java实现 LeetCode 552 学生出勤记录 II(数学转换?还是动态规划?)
- Java动态规划实现最短路径问题
- 动态规划算法(转)
- 数据结构和算法—动态规划
- Leetcode学习计划之动态规划入门day15(62,63)
- Leetcode0393: UTF-8 编码验证(medium, 动态规划)
- 聊一聊双十一背后的技术 - 物流, 动态路径规划
- 基于改进PSO-ABC算法的机器人路径规划(Matlab代码实现)
- 基于PSO优化的路径规划避障系统仿真,沿着障碍物边缘平滑的进行转向
- 64. 最小路径和-动态规划算法
- 714. 买卖股票的最佳时机含手续费-动态规划算法
- [LeetCode] 516. 最长回文子序列 ☆☆☆(动态规划)
- [LeetCode] 64. 最小路径和 ☆☆☆(动态规划)
- [LeetCode] 5. 最长回文子串 ☆☆☆(最长子串、动态规划)
- 最长公共子序列(动态规划、思路)
- HDU 1505 Largest Rectangle in a Histogram && HDU 1506 City Game(动态规划)
- 算法-动态规划 Dynamic Programming--从菜鸟到老鸟 背包问题
- HDU 4044 GeoDefense(动态规划)
- 超八成90后测试员遭遇瓶颈:如何正确规划测试人的职业生涯?
- 动态规划算法模板和demo
- PHP 程序员的技术成长规划