一道和LC-1368很像的Google面试题目

beyondR 发表于 2020-7-8 04:33
我后来想了想，我一开始说的不对。纯DP也可以，根据cost的定义，可以greedy的证明，我们只会向下走和向右 ...

这个例子？最优的不是10->8->7->6->5->4->3->2->1 cost为0？
10 3 2 8 9
8  2  4 3 2
7  6  5 0 1

只往右和下我没发现有cost = 0 的路径

旧未来 发表于 2020-7-8 03:16
没太能够follow你的思路，你的意思是对于任何图中的（i,j）点，到达这点需要的cost是min(四周比它低的点c ...

EMM?我看第二题的意思是求最少的改变的次数？如果是这样的话，按照你说的，应该是对于图中的任何一点（i, j）= min(四周本来就比它低的点，1 + 四周本来比它高的点)， 有个+1是因为从（i, j）出发如果不改一下自己的高度值是到不了四周本来比它高的点的，所以得增加一下自己的高度值。又因为路径是从高到低，所以一个点不会被遍历两次，所以可以加MEM。

旧未来 发表于 2020-7-8 05:11
这个例子？最优的不是10->8->7->6->5->4->3->2->1 cost为0？
10 3 2 8 9
8  2  4 3 2

有道理，那确实不能用纯dp做。就是要dp+search，BFS/Dijkstra是没错的，因为不会走同一个格子两次。至于第一问和第二问有什么区别，我的理解是两者路径不一样的。第一问是考虑周边比本格子低的abs，第二问是考虑比本格子高的abs，

beyondR 发表于 2020-7-8 05:40
有道理，那确实不能用纯dp做。就是要dp+search，BFS/Dijkstra是没错的，因为不会走同一个格子两次。至于 ...

”第一问是考虑周边比本格子低的abs，第二问是考虑比本格子高的abs“ -这个我同意，但区别就是underlying的图不一样，但是依然是dijkstra算？我感觉follow-up不能就这一点区别把

这题的follow-up跟原来的题没啥区别，follow up也是用Dijkstra。要是非用dp的话，可以用bellman-ford那种dp，不过复杂度就太高了，而且也没必要。

第二题的一些想法：
令f i,j,k 表示从终点到(i,j)且当前格子高度为k最小增加量是多少
显然我们枚举k从0到正无穷就可以进行dp（因为k在转移中是不会减少的） 答案就是min{f[0][0][k]}
当然不能这么做，来分析一下f的性质
f i,j,k1[i]- f i,j,k2[i] <= k1-k2 for any k1>k2
所以在转移的时候相邻格子高度要么等于原高度，要么等于当前格子高度+1
所以我们用一个堆来存储f[i][j][k]，大小根据f的值从小到大排序，每次取最小的f出来进行转移
当f[0][0][k]第一次出来的时候就是答案
然后这样做复杂度大概是O(f的状态数）显然还是很多
我们在转移的时候要考虑f i,j,k[i]- f i,j,k'[i] < k-k’ for any k'，如果不满足就不进堆，
这样一来我们可以保证状态中不会又重复的路径（就是a->b->a->c这样）
由于k的值必定要么是原格子高度值，要么是某个格子高度+剩余路径长度，所以
这样一来对于一个格子k至多又(mn)^2种取值（实际应该远远小于这个值）加上我们转移判断需要logmn的时间（使用单调队列）[/i][/i][/i][/i][/i][i][i][i][i][i]再加上堆需要lognm
总的复杂度应该在o((mn)^3log^2(mn)). 当然实际上应该远远小于这个因为k实际上没有这么多[/i][/i][/i][/i][/i]

PocketOffer 发表于 2020-7-8 05:34
EMM?我看第二题的意思是求最少的改变的次数？如果是这样的话，按照你说的，应该是对于图中的任何一点（i, ...

后来想了想，这么做，在不记录路径的时候，还是会出现环。。。哎。

PocketOffer 发表于 2020-7-19 03:51
后来想了想，这么做，在不记录路径的时候，还是会出现环。。。哎。

这个第二问我想明白了，题目意思有点不清楚，正确的意思应该是这样的：
如果我们可以改变grid里的cell里的高度（只能增高），问为了从左上角走到右下角需要改变的高度和的最小值是多少。这个改变是要一次性改变好，例如1->2->3，需要把1和2都变成3，不能1变成2，走到2，然后2走到3。

做法是，从右下角开始做Dijkstra, 然后keep track of the minimal cost to arrive each cell from target, as well as the max-height seen along the path to reach that cell

旧未来 发表于 2020-7-20 04:40
这个第二问我想明白了，题目意思有点不清楚，正确的意思应该是这样的：
如果我们可以改变grid里的cell里 ...

哦？楼主的意思是每次对一个CELL处理的时候，要把之前的COST + MAX(0, CELL的高度 -  MAX HEIGHT HAS EVER SEEN ALONG THE PATH TO REACH THAT CELL)吗？