longest_path.py

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()

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