一个青蛙跳台阶
每个台阶上有个随机数, 比如:
staircase = [11, 22, 44, 5, 12, 34, 55, 45, 23, 64] 给定 n 个台阶和可能跳的步数,比如:
possible_steps = [3,4,5] 对跳到的台阶的数求和,比如:
step_sequence = [3,4] , sum = 44+55 = 99 step_sequence = [4,4,4] , sum = 5+45+(超出台阶算 0) = 50 问和最大的时候是多少? 比如:
best_step_sequence = [3,4,4] , best_sum = 44+55+64 = 163 Example:
Input:
staircase = [11, 22, 44, 5, 12, 34, 55, 45, 23, 64] possible_steps = [3,4,5] Output
163  | 1 lhx2008 Mar 27, 2018 via Android 动态规划问题，只会递归，不太会优化 |
 | 2 vegito2002 Mar 27, 2018 |
 | 3 vegito2002 Mar 27, 2018 今天的题还可以, 虽然还是经典的 DP, 不过不是直接 LeetCode 上面抄来的题目了 V2 插入图片真的是死结了. <img src="http://i67.tinypic.com/2cr60ci.png" width="800"> |
| 4 vegito2002 Mar 27, 2018  |
| 5 vegito2002 Mar 27, 2018  1 每一个 iteration 里面的第二个循环, 需要遍历一个 min_step 的长度, 这个过程可以用一个 min_queue 的 window 来维护, 这样这个遍历就没有必要, amortized O(1) time:  |
| 6 vegito2002 Mar 27, 2018 window 应该返回 max, 上面实现写错了: int windowMax () { return mins.peekLast (); } 对应的调用换一下就行了 |
| 7 vegito2002 Mar 27, 2018 算了, 上面的 minqueue 版本还是有问题, 应该是维护 maxqueue. 不贴图片污染环境了, 直接这个 gist https://gist.github.com/vegito2002/679f0af72ca15b2e9ce1866a6bf4e1a4 |
 | 8 muziki Mar 27, 2018 via iPhone @vegito2002 图片插入貌似只支持 imugr 和 Weibo |
| 9 vegito2002 Mar 27, 2018 @muziki 恩, 刚学会. 第一次贴图片, 以前失败了也都是懒得管 |
Select Language