在Python中的给定矩阵中编程到最长增加路径的长度
假设我们有一个2D矩阵，我们必须找到严格增加的最长路径的长度。要遍历该路径，我们可以向上，向下，向左或向右或对角线移动。
所以，如果输入像
那么输出将为6，因为最长路径为[1、2、4、6、7、9]
为了解决这个问题，我们将遵循以下步骤-
n := row count of matrix , m := column count of matrix
moves := a list of pairs to move up, down, left and right [[1, 0], [-1, 0], [0, 1], [0, -1]]
Define a function dp() . This will take y, x
if x and y are in range of matrix, then
return 0
currVal := matrix[y, x]
res := 0
for each d in moves, do
(dy, dx) := d
(newY, newX) := (y + dy, x + dx)
if newY and newX are in range of matrix and matrix[newY, newX] > currVal, then
res := maximum of res and dp(newY, newX)
return res + 1
From the main method do the following:
result := 0
for i in range 0 to n - 1, do
for j in range 0 to m - 1, do
result := maximum of result and dp(i, j)
return result范例(Python)
让我们看下面的实现以更好地理解-
class Solution:
def solve(self, matrix):
n, m = len(matrix), len(matrix[0])
moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
def dp(y, x):
if y < 0 or y >= n or x < 0 or x >= m:
return 0
currVal = matrix[y][x]
res = 0
for d in moves:
dy, dx = d
newY, newX = y + dy, x + dx
if (newY >= 0 and newY < n and newX >= 0 and newX < m and matrix[newY][newX] > currVal):
res = max(res, dp(newY, newX))
return res + 1
result = 0
for i in range(n):
for j in range(m):
result = max(result, dp(i, j))
return result
ob = Solution()
matrix = [
[2, 4, 6],
[1, 5, 7],
[3, 3, 9]
]
print(ob.solve(matrix))输入值
[ [2, 4, 6], [1, 5, 7], [3, 3, 9] ]输出结果
6