这是一个创建于 2430 天前的主题，其中的信息可能已经有所发展或是发生改变。
一个青蛙跳台阶
每个台阶上有个随机数, 比如:
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 2018-03-27 13:00:40 +08:00 via Android
动态规划问题，只会递归，不太会优化
|
 |
2
vegito2002 2018-03-27 13:36:04 +08:00
|
|
3
vegito2002 2018-03-27 13:38:12 +08:00
今天的题还可以, 虽然还是经典的 DP, 不过不是直接 LeetCode 上面抄来的题目了
V2 插入图片真的是死结了. <img src="http://i67.tinypic.com/2cr60ci.png" width="800"> |
|
4
vegito2002 2018-03-27 13:51:39 +08:00
 |
|
5
vegito2002 2018-03-27 14:21:42 +08:00  1
每一个 iteration 里面的第二个循环, 需要遍历一个 min_step 的长度, 这个过程可以用一个 min_queue 的 window 来维护, 这样这个遍历就没有必要, amortized O(1) time:
 |
|
6
vegito2002 2018-03-27 14:29:44 +08:00
window 应该返回 max, 上面实现写错了:
int windowMax () { return mins.peekLast (); } 对应的调用换一下就行了 |
|
7
vegito2002 2018-03-27 14:33:14 +08:00
算了, 上面的 minqueue 版本还是有问题, 应该是维护 maxqueue. 不贴图片污染环境了, 直接这个 gist
https://gist.github.com/vegito2002/679f0af72ca15b2e9ce1866a6bf4e1a4 |
 |
8
muziki 2018-03-27 14:35:36 +08:00 via iPhone
@vegito2002 图片插入貌似只支持 imugr 和 Weibo
|
|
9
vegito2002 2018-03-27 14:37:02 +08:00
@muziki 恩, 刚学会. 第一次贴图片, 以前失败了也都是懒得管
|
Select Language