算法基础(七):动态规划(二)
1、Help Jimmy http://bailian.openjudge.cn/practice/1661
解题思路:以求解动态规划的思路去思考,即思考子问题是什么以及状态转移方程如何列
子问题即从板的左端到地面和右端到地面的最短时间
所以计算每个板的最短时间时分为左端和右端时间来求取
求LeftMinTime:
当左下方没有板子时,即下方为地面,这时有两种情况,一是距地面距离小于安全距离,可以安全下落,时间可得;二是距离大于安全距离,游戏结束,所以为正无穷
当左下方是板子时,即下方可以到达另一块板子,则该板子的最短距离等于下一块板子的左端时间或右端时间的最短时间,此时注意走到板子另一端的时间和下落时间别忘记了!
注意,对板子进行编号,即需要判断下方是否还有板子
2、滑雪
递归求解时,非常简单,设置好边界条件,即四周没有比他小的时设置为1;其他情况沿着四个方向走,返回最大的
递推求解,每次走L大的,但是比他低的
3、神奇的口袋
是否选择第K种物品,选择加上不选择就是全部的选择方法