数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python 中给定矩阵中找出最长递增路径的程序
假设我们有一个二维矩阵，我们必须找到最长严格递增路径的长度。要遍历路径，我们可以上下左右移动，不能斜着移动。
所以，如果输入如下
| 2 | 4 | 6 |
| 1 | 5 | 7 |
| 3 | 3 | 9 |
那么输出将是 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
更新日期： 12-12-2020
105 次浏览
广告