(Atcoder)Educatoinal DP Contest G-Longest PathをPythonで

メモ化再帰DPの動きについての備忘録です。勉強勉強・・・
こんな短いコードにいろいろ詰まってるなぁ・・・

ポイント

トポロジカルソートってやつでできるみたいだけど、メモ化再帰DPの方が楽らしい

DP遷移イメージ

コード

import sys
sys.setrecursionlimit(10**5+10)
def memo(v):
    if dp[v]!=-1:return dp[v]
    ans = 0
    for next_v in graph[v]:
        ans = max(ans,memo(next_v)+1)
    dp[v] = ans
    return ans

n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x,y = map(int,input().split())
    graph[x].append(y)
    
dp = [-1]*(n+1)

ans = 0
for v in range(1,n+1):
    ans = max(ans, memo(v))
    
print(ans)