求解下 Dropbox Sharpness value 的解法

粘贴下另一个帖子里的描述：https://www.1point3acres.com/bbs/thread-231002-1-1.html

输入一个 2-D array，比如说是：
4    5    4    0    1    2
5    6    5    0    0    0
0    0    0    0    0    0
1    3    1    2    3    3
3    0    3    0    0    0

从最左一列中的任意一个出发，到达最右一列的任意一个，要求：
1）当前格子要想往右走，只能往右上、右边、右下三个格子移动；
2）一条path中最小的那个值才是这条path的合格value；
3）在所有path中找到合格value最大的那一条，输出它的value。

比如给的上面这个例子中，我把最后的path标出来了：3->3->3->2->3->3，所以最终结果就应该返回2。
而比如第一行的path：4->5->4->0->1->2，合格value应该是0，所以不是最终结果。

DP 公式：

1. dp[i][j] = min(max(dp[i-1][j-1], dp[j-1], dp[i+1][j-1]), grid[i][j])

复制代码

[i][i]
我理解是看(i)(j) [i]的右边三个点，但是min 和 max 这里怎么解释呢？谢谢。

下面是完整题目：

[/i][/i][/i]

union find 好像也可以做

就是经典的dp吧
假设v[i][j]是原始值，p[i][j]是每一个点的max path value

第一列init，p值就是v值
从左向右扫描，每一个点有最多3个path，每个path的value是min(p[i-1][k], v[i][j])，k=j-1,j, j+1,注意检查边界
p[i][j]就是上面3个path里面最大的那个
最后统计最右边那行的最大p

谢谢楼上的回答。自己又想了下，主要是不理解为什么 先取 max 再取 min。想通了，下面是我的推理思路：