Skip to content

Instantly share code, notes, and snippets.

@lttzzlll
Last active May 17, 2018 08:17
Show Gist options
  • Save lttzzlll/2a6268a4a11b8d0f0eba1bcf20f9476b to your computer and use it in GitHub Desktop.
Save lttzzlll/2a6268a4a11b8d0f0eba1bcf20f9476b to your computer and use it in GitHub Desktop.
import unittest
def dp(nums, m, n, i, j, visit):
ll, uu, rr, dd = [], [], [], []
if i - 1 >= 0 and not visit[i - 1][j] and nums[i - 1][j] < nums[i][j]:
visit[i][j] = True
uu = dp(nums, m, n, i - 1, j, visit)
if j - 1 >= 0 and not visit[i][j - 1] and nums[i][j - 1] < nums[i][j]:
visit[i][j] = True
ll = dp(nums, m, n, i, j - 1, visit)
if i + 1 < m and not visit[i + 1][j] and nums[i + 1][j] < nums[i][j]:
visit[i][j] = True
dd = dp(nums, m, n, i + 1, j, visit)
if j + 1 < n and not visit[i][j + 1] and nums[i][j + 1] < nums[i][j]:
visit[i][j] = True
rr = dp(nums, m, n, i, j + 1, visit)
res = []
if len(ll) > len(res):
res = ll
if len(rr) > len(res):
res = rr
if len(uu) > len(res):
res = uu
if len(dd) > len(res):
res = dd
return res + [nums[i][j]]
def longest(matrix):
m = len(matrix)
n = len(matrix[0])
record = [[0 for i in range(n)] for j in range(m)]
for i in range(m):
for j in range(n):
visit = [[False for i in range(n)] for j in range(m)]
record[i][j] = dp(matrix, m, n, i, j, visit)
res = []
for row in record:
for cell in row:
if len(cell) > len(res):
res = cell
return res
class TestLongest(unittest.TestCase):
def test_longest(self):
nums = [[9, 9, 4],
[6, 7, 8],
[2, 1, 1]]
longest_path = [1, 2, 6, 7, 9]
res_path = longest(nums)
self.assertEqual(len(longest_path), len(res_path))
print(longest_path, res_path)
if __name__ == '__main__':
unittest.main()
@lttzzlll
Copy link
Author

找到一个最长递增路径 [1, 2, 6, 7, 8] or [1, 2, 6, 7, 9]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment