Snapchat 电面

godstears 发表于 2016-4-19 21:01
对的
我少打了个
dp[v] = dp[v - 1] || dp[v] || dp[v + 1]

你好，我想问下写dp的循环时这个v的范围是怎么确定的呢？谢谢~

jy_121 发表于 2016-4-20 01:43
你好，我想问下写dp的循环时这个v的范围是怎么确定的呢？谢谢~

我是直接 0到总长度， 面试官最后说怎么shrink我说那就到 i 吧， 他问了一下为什么我说了一下最多考虑都到前面 i 步？他好像默认对了， 可是我回来试了一下错的lol，你试出来跟我说一下吧

jialegavin 发表于 2016-4-19 13:40
我觉得楼主的公式可能打错了。少了个。我说说我的想法，如果不对请楼主指正哈~明天我也正要面snapchat。
...

类似背包问题吧？

楼主初始化L[0][j]和L[k][0]的?谢谢

godstears 发表于 2016-4-20 01:47
我是直接 0到总长度， 面试官最后说怎么shrink我说那就到 i 吧， 他问了一下为什么我说了一下最多考虑都 ...

好的，不过我也没想明白。。。

TsengJuiWang 发表于 2016-4-20 05:37
楼主初始化L[0][j]和L[k][0]的?谢谢

初始化就一位: dp[0][1] = 1表示在位置0而且当前的velocity是1

godstears 发表于 2016-4-20 06:04
初始化就一位: dp[0][1] = 1表示在位置0而且当前的velocity是1

楼主，我在网上看到这个题，和你的很像，但是写法好像不太一样http://algorithmsgeek.blogspot.com/2013/06/algo28-help-frog-to-cross-river.html

TsengJuiWang 发表于 2016-4-20 07:07
楼主，我在网上看到这个题，和你的很像，但是写法好像不太一样http://algorithmsgeek.blogspot.com/2013/ ...

有点长啊，我就两个for loop再一个公式， 20行吧

godstears 发表于 2016-4-20 07:10
有点长啊，我就两个for loop再一个公式， 20行吧

我是觉得你俩的等式不一样，他是L[i][j] = L[i - j][j] || L[i - j][j - 1] || L[i - j][j + 1]，另外j的取值范围我看了他的代码之后想了一下应该是sqrt(2*n)因为第一次速度是1，下一次速度最大是2，可以跳到3，下一次速度最大是4，最远可以跳到7，也就是(1 + v) * v / 2 = n，所以v~sqrt(2n)

补充内容 (2016-4-20 07:21):
L(i,j) i又被吞了

TsengJuiWang 发表于 2016-4-20 07:20
我是觉得你俩的等式不一样，他是L[j] = L[j] || L[j - 1] || L[j + 1]，另外j的取值范围我看了他的代码之 ...

这个公式肯定不对吧