動的計画法

ここ数日，動的計画法の練習をしている．漸化式の立て方のコツが分からず苦戦していたのだが，kinaba 先生の動的計画法の考え方を読んだことがきっかけで，大分理解が進み，漸化式の立て方が分かってきた．漸化式も，問題から自明に導くというよりも，計算結果のキャッシュを使うように部分問題を展開するという点がポイントであると思った．一旦キャッシュをりようできるように漸化式を立ててしまえば，その通りにループを記述するだけなので，シンプルに記述できる．