2018027 今日算法

[ljy2010a]

一个青蛙跳台阶
每个台阶上有个随机数, 比如:

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

[lhx2008]

动态规划问题，只会递归，不太会优化

[vegito2002]

http://i67.tinypic.com/2cr60ci.png

[vegito2002]

今天的题还可以, 虽然还是经典的 DP, 不过不是直接 LeetCode 上面抄来的题目了

V2 插入图片真的是死结了.

<img src="http://i67.tinypic.com/2cr60ci.png" width="800">

[vegito2002]

[vegito2002]

每一个 iteration 里面的第二个循环, 需要遍历一个 min_step 的长度, 这个过程可以用一个 min_queue 的 window 来维护, 这样这个遍历就没有必要, amortized O(1) time:

[vegito2002]

window 应该返回 max, 上面实现写错了:

int windowMax () {
return mins.peekLast ();
}

对应的调用换一下就行了

[vegito2002]

算了, 上面的 minqueue 版本还是有问题, 应该是维护 maxqueue. 不贴图片污染环境了, 直接这个 gist


https://gist.github.com/vegito2002/679f0af72ca15b2e9ce1866a6bf4e1a4

[muziki]

@vegito2002 图片插入貌似只支持 imugr 和 Weibo

[vegito2002]

@muziki 恩, 刚学会. 第一次贴图片, 以前失败了也都是懒得管