原题
给定一个整数矩阵（其中，有 n 行， m 列），请找出矩阵中的最长上升连续子序列。（最长上升连续子序列可从任意行或任意列开始，向上/下/左/右任意方向移动）。
样例
给定一个矩阵
[
[1 ,2 ,3 ,4 ,5],
[16,17,24,23,6],
[15,18,25,22,7],
[14,19,20,21,8],
[13,12,11,10,9]
]
返回 25
解题思路
- 类似于滑雪问题
- 记忆化搜索 - 因为对于某一个点，可以从上下左右更新，所以很难写出for循环那种DP
- 所谓记忆化所有，就是当我想更新matrix[x][y]的时候，我需要知道以matrix[x-1][y], matrix[x][y-1], matrix[x+1][y], matrix[x][y+1]这四个点结尾的最大长度，每次求出以matrix某个点结尾的连续的最大长度之后，都记录下来，下一次先去记忆的matrix中找，没有再算，有的话直接返回值
完整代码
class Solution:
# @param {int[][]} A an integer matrix
# @return {int} an integer
DIRECTIONS = [(1, 0), (0, 1), (0, -1), (-1, 0)]
def longestIncreasingContinuousSubsequenceII(self, A):
# Write your code here
if len(A) == 0 or len(A[0]) == 0:
return 0
self.width = len(A[0])
self.height = len(A)
self.matrix = [[0 for i in range(self.width)] for j in range(self.height)]
for i in range(self.height):
for j in range(self.width):
self.search(A, i, j)
return max(max(row) for row in self.matrix)
def search(self, A, x, y):
if self.matrix[x][y] != 0:
return self.matrix[x][y]
longest = 1
for dx, dy in self.DIRECTIONS:
if x + dx < 0 or x + dx >= self.height:
continue
if y + dy < 0 or y + dy >= self.width:
continue
if A[x][y] >= A[x + dx][y + dy]:
continue
longest = max(longest, self.search(A, x + dx, y + dy) + 1)
self.matrix[x][y] = longest
return self.matrix[x][y]
