新鲜出炉的Google电面

刷题不精，fail了太多次onsite，这次连电面都省不了了，还遇到一道没见过的题。。。

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

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

问得分最大的走法是啥，返回最大得分。

想用dp做，但是毫无头绪，最后写了一个brute force。。。。想请教一下各位大神，看看对这题有什么想法，能给lc题号最好了，谢谢

dp[i][j]=max(dp[i-1][x]+m[i][j]-|j-x|)

https://www.1point3acres.com/bbs ... ;page=1#pid13510737
看这个贴子，我之前详细解释过

我感觉再找最大的dp[i][j]的时候并不需要把dp[i-1]全试一遍


比如dp[i - 1] = [1, ......., 2, 4，．．．．], 对于２左边的ｊ，４肯定比２好，这样你没一层可以ｐｒｅｐｒｏｃｅｓｓ一下每个ｊ最好的左边和最好的右边，到时候就可以直接用上

好家伙，上来就是dp

dp也是O(n^3)嘛。

yulian 发表于 2021-3-18 07:04
dp也是O(n^3)嘛。

应该是n2 然后可以优化，但是我不知道怎么优化

只想到了O(N^3)的DP。
空间可以压缩到O(N)，N是matrix的宽度。

copper1820 发表于 2021-3-18 07:41
应该是n2 然后可以优化，但是我不知道怎么优化

反正我想不出n^2的算法。

copper1820 发表于 2021-3-18 07:41
应该是n2 然后可以优化，但是我不知道怎么优化

这题怎么n ^ 2？

ljhgod 发表于 2021-3-18 06:57
dp[j]=max(dp[x]+m[j]-|j-x|)

dp[i][j]=max(dp[i-1][x]+m[i][j]-|j-x|) 这里面有i，j,  x,
x 代表的是啥？找出x是什么复杂度？