西瓜の備忘録

競プロとかで気づいたこととか考察を書き留めるためのブログ

yukicoder No.92を解いた

 

No.92 逃走経路 - yukicoder

DPで解いた

dp[i][j]:=i(<K)回道を通ったときにj番目の街にいるかどうかという2次元配列を作って0で初期化

最初の1回目はd1に一致する町全てに1を代入(開始地点は任意のため)

i(1<i≦K)回目はi-1回目にいる可能性のある町から行ける町に1を代入すれば良い