一道Hulu DP 面试问题

从这里看到的。
Ads Fatigue（给n个slots，让插入一个广告x，保证x之间的gap大于一个值k，用dp秒之，和house robber有点像）

就是比如3个slot _ _ _
gap是1
你可以这么放
x _ x.
x _ _.
_ x _.
_ _ x
_ _ _
一共5种

看描述，这个题问的应该是最多的摆放方式。

请问该怎么用dp做呢？我想不明白。 请各位大神指教。

求方案数
f[i]表示前i个slot的总方案数
f[i] = f[i - 1] (不放) + f[i - k - 1] (放)

求最多放几个
f[i]表示前i个slot的答案
f[i] = max{f[i - 1] (不放) , f[i - k - 1] + 1 (放)}

QDkAc 发表于 2017-1-26 11:24
求方案数
f表示前i个slot的总方案数
f = f (不放) + f (放)

谢谢你的解答。但怎么init 这个dp array呢？
拿3个slot的例子，如果求方案数的话，
f[0] = 1 （f[0] 设为1，不知道是否合适。）
f[1] = 1
f[2] = f[1] + f[0] = 2
f[3] = f[2] + f[1] = 3  但这里并不等于5啊？

f[1]是2啊兄弟

QDkAc 发表于 2017-1-26 12:10
f[1]是2啊兄弟

明白了！谢谢了！

能问下，这题怎么想到用DP的吗？

DWill008 发表于 2017-1-26 13:12
能问下，这题怎么想到用DP的吗？

多做题就有感觉了

QDkAc 发表于 2017-1-26 18:22
多做题就有感觉了

谢谢你的解答…… 我还特意去做了一下leetcode上的house robber 1和2.
想请问这这种题目在没有OJ的情况下如何验证自己的code是否正确呢。。？

QDkAc 发表于 2017-1-26 18:22
多做题就有感觉了

你觉得我应该去想corner case然后去一个个测？

楼主 求hulu面经 能分享一下么 谢谢！！