資料結構
網路
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 次瀏覽
廣告