G - Longest Path
#DP-G
#AtCoder解答メモ
#DP
#トポロジカルソート
問題
https://atcoder.jp/contests/dp/tasks/dp_g
考察
状態定義
dp[i]
= ノードiを始点とする経路の最大長
遷移
dp[i]
= ノードiを始点とするノードjの最大経路長 + 1
遷移の順番がi=1, 2, 3... Nの順ではないので、ループよりも
メモ化再帰
で書く方が実装しやすい
シミュレーション
入力例1
https://gyazo.com/ccbc9ec7a01cecaadf93903974533930
処理の流れ
実装
https://atcoder.jp/contests/dp/submissions/20948686
実装上の注意
所感
参考