Google onsite 面经

第一题是dp吧，只能从top往下取，dp[i][j]表示前i堆取j个的最大值，转移：for k in 0...size[i+1],  dp[i][j] = max(dp[i][j], dp[i-1][j - k] + value[i][k])

第一题可以用递归解，或者可以建立一个dp的matirx，这个是最好的。要注意考虑pile的金币数量不同的问题。

第六题就是rmq的变种，存的就是区域内的最大值，但是只是list不可变的情况
如果list可变，可以用线段树做

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

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

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

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

祝lz早日拿到offer

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

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

多谢指正，想的不周全，backtrack确实比较直观

Yoyo00 发表于 2016-5-6 06:42
能请问一下第一题怎么做吗

等价于所有队列的最大前缀和的和， 约束是满足前缀下标和为n

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

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