import sys, copy
from collections import deque
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
max_ans = -sys.maxsize
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]
# dp[i][j] = (i,j)에서 갈 수 있는 루트 중 제일 길게 갈 수 있는 루트 길이
dp = [[-1]*n for _ in range(n)]
def dfs(y, x):
if dp[y][x] != -1:
return dp[y][x]
dp[y][x] = 1
for i in range(4):
ny, nx = y + dy[i], x + dx[i]
if 0 <= ny < n and 0 <= nx < n:
if graph[ny][nx] > graph[y][x]:
dp[y][x] = max(dp[y][x], dfs(ny, nx)+1)
return dp[y][x]
for i in range(n):
for j in range(n):
max_ans = max(max_ans, dfs(i, j))
print(max_ans)
그냥 DFS를 다 돌리면 시간 초과가 난다.
이번에도 역시 점화식이 중요했는데, dp[i][j]를 (i,j)에서 출발해서 갈 수 있는 루트 중 가장 긴 루트의 길이라고 하자. 그러면 이미 dp[i][j]는 최적해라는 것이 보장되었기 때문에, 다른 지점에서 길을 찾다가 (i,j)에 도착하면 dp[i][j]를 그대로 쓰면 된다.