dpテーブル作って考えたほうがわかりやすいと思います
https://www.nii.ac.jp/userdata/shimin/documents/H22/100805_3rdlec.pdf
これの19ページとか