之前我们讲到动态规划五步中有个Guessing猜，一般情况下猜有两种情况：

• 在猜和递归上：猜的是用于解决更大问题的子问题；
• 在子问题定义上：如果要猜更多，就要增加更多子问题。

下面我们来看如果像背包问题那样子问题比较多，该怎么去解决？

一、Piano / Guitar Fingering

给定n个按键，找到每个键应该用哪只手指去按。假设有F个手指，刚开始手指f按在p键上，如果转移到用手指g按键q，这个转移难度为定义为d(p, f, q, g)。

动态规划的解决思路如下（红叉内的内容是因为只考虑了一个子问题而报错）：

上面是“单次按键只能按一个键”，但实际上，单次按键会要同时按多个键或弦，这该怎么办呢？方法如下图所示：

二、俄罗斯方块

如果你玩俄罗斯方块有下列前提，你该如果用动态规划去设计算法？结果如下图：

三、超级玛丽奥

在超级玛丽奥上，动态规划的子问题就更多了，需要考虑最小化时间，最大化分数，最大化玛丽奥速度等，解决思路讲师没给出来，但方法都八九不离十，这里我就没进行深入了解了，后续有兴趣可以深入了解看看。

最新文章

1. mysql开启远程访问权限
2. 05.virsh命令的常用操作(kvm)
3. 服务链（Service Chaining，or Service Function Chaining，SFC，功能服务链）
4. Redis入门指南
5. ListView、PullToRefreshListView滑动加载可见item
6. php 表单提交
7. 矩阵奇异值分解(SVD)及其应用
8. android学习笔记十——TabHost
9. [HDU 1254] 推箱子
10. Cocos2d-x3.0游戏实例之《别救我》第四篇——乱入的主角
11. iOS 多线程开发之OperationQueue（二）NSOperation VS GCD
12. Docker集群实验环境布署--swarm【4 管理组件--manager】
13. push以及pop，shift，unshift
14. 【Centos】解决设置JAVA_HOME不断失效问题
15. POJ-1573 Robot Motion模拟
16. python-tqdm进度条
17. 2018-2019-1 20189201 《LInux内核原理与分析》补漏_1125写
18. Jmeter分布式部署- linux
19. String.split()与StringUtils.split()
20. arch Linux（一）

热门文章

1. 使用appium后安卓手机无法调出键盘解决方法
2. linux(centos8):安装分布式事务服务seata(file单机模式,seata 1.3.0/centos 8.2)
3. selenium分布式启动(deepin)
4. dhtmlxSpreadSheet开源电子表格小部件创建教程
5. Python函数递归调用
6. 想买保时捷的运维李先生学Java性能之 运行时数据区域
7. 了解Js中的client，offset
8. JS的各种数据类型
9. vscode按下F5黑窗口显示的是乱码
10. 重新开始记录java教程