1109 Google 电面 全职

发面经攒人品！！！！GG我现在是一路黑到底了！！！去年被烙印黑了一次，今年被放了一次鸽子，今年又被烙印黑！！！！电话迟到十分钟打来，提前十分钟结束，总共四十分钟。面试官全程一句话都不说，贴了题目，问我你明白我们要找什么了，我说明白了，然后就没有任何声音了。

今天的店面，只有一道题目：给一个矩阵，找一条从第一行到最后一行的和最大的路径。可以从第一行任意位置开始，但是只能向下往相

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

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

(2016-11-11 00:43):
HR电话里跟我说挂了，二十四小时之内给feedback还是挺快。我说面试官全程任何feedback都没给我，hr说她收到的feedback就是这样，认为我还不够。

这个找路径用dp也行吧，一维数组记录最大值，2维数组记录当前行到下一行的index位置

类与对象tju 发表于 2016-11-11 08:05
这个找路径用dp也行吧，一维数组记录最大值，2维数组记录当前行到下一行的index位置

用两个一维数组做记录。
从最后一行开始，往上计算每行每个位置到最后一行的最大值。

tjcd 发表于 2016-11-10 10:45
这是CV里面一道经典的DP题 reference: "Seam Carving for Content-Aware Image Resizing"

难怪觉得似曾相识，但是我曾经图像处理的课整个是逃过去的。。

没看懂，3，5,9不是在都在第一行吗，为什么是和最大的路径

补充内容 (2016-11-10 09:12):
懂了，忽略我~

烙印这么过分吗

相邻的意思是向左向右都可以吗还是说只能向右。。。。向左向右都可以感觉DP很难写啊

prodigalr 发表于 2016-11-10 09:16
相邻的意思是向左向右都可以吗还是说只能向右。。。。向左向右都可以感觉DP很难写啊

三种情况，左右下

xhlzyllx 发表于 2016-11-10 09:15
烙印这么过分吗

是，我全程都在说，听不见对方一句话，还被提前挂掉电话，我还没解释完。
去年GG面实习的那个烙印稍微好点。

相邻表示，向左下，向下，向右下

求问楼主怎么做的。如果是三个方向，不是就变成dp[i][j] = max(dp[i][j-1], dp[i][j+1], dp[i-1][j]) + matrix[i][j]，这个感觉会死循环啊。求指导！

补充内容 (2016-11-10 09:23):
忽略我，看了楼主更新的定义了～

这是CV里面一道经典的DP题 reference: "Seam Carving for Content-Aware Image Resizing"

LZ已经不错了，我估计当场都不一定写的出来。