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

在蠡口上看到有人讨论的一个题目, 想搬运过来和大家讨论一下

Q: Given a m-by-n matrix containing positive numbers, you start from top left and travel towards bottom right. You can move in either up, down, left, or right directions. When moving from a higher number to lower or equal number, the cost is 0. When moving from a lower number to a higher number, the cost is the absolute difference. Find and return the minimum cost from top left to bottom right of the matrix.

Follow-up: Given the same m-by-n matrix, however, this time you can only move from a higher number to lower number. You can increase any number so that you can move to the next number. Find and return the minimum amount to increase in order to move from top left to bottom right of the matrix.

第一问Dijkastra应该可以轻松handle，但是看到讨论有说DP可以做，我没太想明白DP怎么处理四个方向都可以走的情况，难道是做一次从左上到右下的DP,然后再做一次右下到左上的DP,一直重复这个过程直到DP的table稳定不变了？
紧接这第二问有点像LC 174. Dungeon Game，但是需要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-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-8 03:16
没太能够follow你的思路，你的意思是对于任何图中的（i,j）点，到达这点需要的cost是min(四周比它低的点c ...

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

能不能把lc讨论的原链接贴一下？

第二题，如果是用DP的话，虽然是四个方向都可以走，但是因为规定了只能从大走到小，所以其实也是个不会产生循环的图-》所以也是也能用DP的吧？对于每一个点来说，先不改自己的值，通过往本来就比自己小的邻居得到一个解， 然后再改了自己的值（直接在GRID里改？？），通过本来比自己大的邻居得到另一个解，两个解比较一下，取小的。至于怎么利用DP，就拿横纵坐标当做MEM参数？？？？

zszszszs

beyondR 发表于 2020-7-8 02:22
能不能把lc讨论的原链接贴一下？

https://leetcode.com/discuss/int ... e-june-2020-pending

这个的round 4

PocketOffer 发表于 2020-7-8 02:51
第二题，如果是用DP的话，虽然是四个方向都可以走，但是因为规定了只能从大走到小，所以其实也是个不会产生 ...

没太能够follow你的思路，你的意思是对于任何图中的（i,j）点，到达这点需要的cost是min(四周比它低的点cost + 高度差, 四周比它高的点的cost)?

thanks for the link。这道题纯dp应该是做不了的。需要nxm的DP array和graph search相结合。我个人是觉得用diksja做就可以。followup和lc1368完全一样，稍微改一下cost改变的条件就行，我个人会用heap+bfs做啦，复杂度稍微高一些。DP+graph search应该可以达到nm的复杂度。

beyondR 发表于 2020-7-8 03:26
thanks for the link。这道题纯dp应该是做不了的。需要nxm的DP array和graph search相结合。我个人是觉得用 ...

其实这题第一问和第二问有什么本质区别吗？没太想明白这个地方
我的理解是第一问从高到低 ，edge weight  = 0, 从低到高，edge weight = diff
第二问，从高到低 ，edge weight  = 0，  从低到高，只需要把低的增到和高的一致就行，weight也是diff

旧未来 发表于 2020-7-8 03:52
其实这题第一问和第二问有什么本质区别吗？没太想明白这个地方
我的理解是第一问从高到低 ，edge weight ...

我后来想了想，我一开始说的不对。纯DP也可以，根据cost的定义，可以greedy的证明，我们只会向下走和向右走，不会向上和向左。所以直接dp做就可以

got this one last November ... didn't solve it