atcoder diverta 2019 Programming Contest 2 E問題

問題E https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_e

なぜか、この問題の解説を聞いていると

強化学習の時のV(S)を求める計算 bellman equationとリンクしたので

V(S) = MAXa ( R(s, a) + γV(s'))

メモ。

という問題

解説動画　60:00

DP問題の起源はRechardさんで、

本質的に、その状態の価値を計算するもの。

その状態において最適なアクションを起こし続けた時、最終的に得られる価値は

これなので、現在のこの状態における価値はこれだよね。

という計算。

平たく言うと、

現在の状態での最大の価値。

だからの、特定の状態の時の最大を保存し続けて行って、徐々に入力値をもうらしていくのがDP

pdfの解説はこちら

以上です。