動的計画法解説 [SRM 468 Div2 250/Div1 500] 目次 問題1(入門編) 全探索 再帰と漸化式 メモ化再帰 動的計画法 問題2(初級~中級編) 全探索 再帰と漸化式 動的計画法 問題1 王様は長い間出張していたので、できるだけ早く女王のもとに帰りたいと思っています。王様は都市 0 におり、女王は都市 N (1 <= N <= 50)に居ます。全ての都市 i (0 <= i <= N - 1) に対して陸路と空路があります。配列 roadTime, flightTime が与えられ、それぞれの i 番目の要素は都市 i から都市 i + 1 までの陸路、空路の所要時間 (1 以上 1000 以下) を表わします。しかし王国の科学力は低く、空路による移動は墜落の危険を伴います。そのため、王女は王様に空路は K (0 <= K <= N) 回までに留めるように言いました。王