Google onsite 面经

楼主，求问一下，第二题 subtree pair好像 面试中总喜欢问道，但是我还是对题目没那么清晰。能不能再加点描述？ input output具体是什么呢？ 万分感谢！

CrossTheWall 发表于 2016-5-6 16:03
是啊，第三题是这几个里面最送分的题目。其他几个多少都有坑的。。。 尤其第一个直接可以转化成一个操作 ...

这个必须DP呀，{2, 3, ...} 跟 {3, 2, ...}的后续计算是重叠的，直接backtracking肯定上指数级别了。

您好！
本帖隐藏的内容需要积分高于 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

楼主可以三句话简单讲讲第一题的dp解法吗？谢谢

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

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

william_gong 发表于 2016-8-2 12:49
第一题的dp， 有人能帮忙看看吗？

能解釋一下嗎

感謝

william_gong 发表于 2016-8-2 12:49
第一题的dp， 有人能帮忙看看吗？

res应该不用比较每个(i,j), 比较最后一列就行

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

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

william_gong 发表于 2016-9-9 21:48
dp[j] 表示在前i列硬币里取j个硬币最多可以取到多少钱

补充内容 (2016-9-9 21:51):

只能从上往下取吧，不能越级取