Python 中矩阵的最长递增路径
假设我们有一个矩阵;我们必须找到最长递增路径的长度。从每个单元格,我们可以向四个方向移动——左、右、上或下。我们不能对角移动或移出边界。
因此,如果输入如下
| 9 | 9 | 4 |
| 6 | 6 | 8 |
| 2 | 1 | 1 |
则输出将为 4,因为最长的递增路径是 [3, 4, 5, 6]。
为了解决这个问题,我们将遵循以下步骤 −
定义一个函数solve()。这将需要 i,j,matrix
如果 dp[i,j] 非零,则
返回 dp[i, j]
dp[i, j] := 1
temp := 0
对于 i-1 到 i+2 范围内的 r,执行
对于 j-1 到 j+2 范围内的 c,执行
如果 r 与 i 相同且 c 与 j 相同或(|r-i| 与 1 相同且 |c-j| 与 1 相同),则
继续下一个迭代
如果 c>=0 且 r>=0 且 r< 矩阵的行数且 c < col 矩阵[0] 的大小和 矩阵[r, c]>矩阵[i, j],则
temp := temp 的最大值,求解(r, c, 矩阵)
dp[i, j] := dp[i, j] + temp
返回 dp[i, j]
从主方法执行以下操作 −
如果矩阵不为零,则
返回 0
dp := 与给定矩阵大小相同的矩阵并填充0
ans := 0
对于 i 在 0 到矩阵大小的范围内,执行
对于 j 在 0 到矩阵[0]大小的范围内,执行
如果 dp[i, j] 与 0 相同,则
solve(i, j, matrix)
返回 ans
示例
让我们看看下面的实现以便更好地理解 −
class Solution(object): def solve(self,i,j,matrix): if self.dp[i][j]: return self.dp[i][j] self.dp[i][j] = 1 temp = 0 for r in range(i-1,i+2): for c in range(j-1,j+2): if r==i and c==j or (abs(r-i)==1 and abs(c-j)==1): continue if c>=0 and r>=0 and r<len(matrix) and c<len(matrix[0]) and matrix[r][c]>matrix[i][j]: temp = max(temp,self.solve(r,c,matrix)) self.dp[i][j]+=temp return self.dp[i][j] def longestIncreasingPath(self, matrix): if not matrix: return 0 self.dp = [ [0 for i in range(len(matrix[0]))] for j in range(len(matrix))] self.ans = 0 for i in range(len(matrix)): for j in range(len(matrix[0])): if self.dp[i][j]==0: self.solve(i,j,matrix) self.ans = max(self.ans,self.dp[i][j]) return self.ans ob = Solution() print(ob.longestIncreasingPath([[9,9,4],[6,6,8],[2,1,1]]))
输入
[[9,9,4],[6,6,8],[2,1,1]]
输出
4
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

