Tiktok OA q2 就是个DP, 大家再耐心想想

Tiktok OA q2 就是个DP, 大家再耐心想想. 不要一窝蜂看到个论文就激动. 面试题肯定是用正统思路能做出来, 不会因为你

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

二维表, 难点是如何定义每个格子的含义, 以及如何单位时间求每个格子.

我的思路是 第二题其实用dp就可以应对大部分的情况，时间复杂度大概是O(n * m * k)。无法用dp解决的是n, m, k都很大的时候，这种情况下其实ituitively就可以觉得概率是1，比如test case 3给的就是n, m, k都是1000的情况。这种情况下其实可以用中心极限定理去近似，k很大的时候 如果n小于均值减去5倍标准差就可以认为概率是1。

楼主这么说，也是没搞清楚这题。这题dp并不难想，但是只能解决M<=10, K<=10这个量级的。这题难点是1000^1000这么大的数怎么处理。这时候这题真的就是纯数学问题了。

题呢lz？

带佬对第三题有什么想法？是不是也是个dp？

关键是他题目里面有句话 feel free to try out closed form, simulation, .... 这才导致大家全去找closed form，这种hint不提出标准思路也不至于误导大家吧。内卷王实至名归。

dp蜀黍很容易想，但会overflow

求问Q3怎么做啊。我总是TLE。。。

楼主DP test case 全通过了么？谢谢！

Dp时间复杂度怕不是要死。。

请问楼主是几维dp呢？是不是N，M，K都要，然后用个三维DP？