好像是谷歌面试题…中比较弱智的
- 输入: 一个m*n矩阵ary, 矩阵元素只有0和1
- 输出: 寻找从左上到右下的连续路径中最长的路径长度(也就是只能往右或往下或往右下走)
- 定义: 只要1的周围8个点有1就定义为连续路径
- 状态矩阵定义: $dp[i][j]$代表在$ary[:i][:j]$子矩阵中, 经过点$arr[i][j]$的路径的最大值
- 状态转移方程:
$$ dp[i][j] = \begin{cases} max \lbrace & dp[i-1][j], \\
& dp[i][j-1], \\
& dp[i-1][j-1] \rbrace + 1, & ary[i][j] = 1 \\
0, && ary[i][j] = 0
\end{cases}$$ - 首先计算出dp第一行第一列的值, 再从左向右从上到下计算整个dp数组, 最后统计最大值即可
|
拓展:
如果允许往任意方向走, 那就成了一个搜索最大的连通分量的题