新鲜谷歌Onsite面经

火火火bit

Josh 发表于 2016-9-9 12:59
记得之前面经见过一道题跟楼主第二题很像：给n堆硬币，每次只能从堆顶拿一枚，问拿k个硬币最大数额是多少。 ...

求解。。能想到用记忆化搜索来剪枝，但复杂度不会分析

superbeet

Josh 发表于 2016-9-9 12:59
记得之前面经见过一道题跟楼主第二题很像：给n堆硬币，每次只能从堆顶拿一枚，问拿k个硬币最大数额是多少。 ...

在哪里看到的？

daniel_hl

diff那个是类似于edit distance吗

william_gong

superbeet 发表于 2016-9-9 13:59
在哪里看到的？

william_gong

火火火bit 发表于 2016-9-9 13:51
求解。。能想到用记忆化搜索来剪枝，但复杂度不会分析

你的记忆化搜索打算纪录哪些状态呢？

superbeet

有坛友了解碰到"面试官迟到很久面试很仓促"这种情况，应该怎么处理呢？

zzgzzm

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

zzgzzm

楼主可以再具体澄清一下“N次操作后能拿到的数字和最大是多少” 是怎么定义的吗？在初始状态下我们是否可以知道每个stack中所有元素的值？还是只能通过stack::peek只知道顶端的值？

南慕伦

dp啦
dp[i][j]表示前i个栈取j个数字的最大值
显然dp[i][j] = max{dp[i-1][k] + sum[i][0..(j-k-1)]}
边界条件就是dp[0][j] = 0

zzgzzm

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