アルゴリズムイントロダクション
15.1.1
ノートに書いた
15.1.2
ri(j+1)=2^(n-(j+1))と仮定して置き換え法。i=1のときについて解いてあとは対称性から２についても成り立つことを考える。
15.1.3
等比数列の和の公式使えばできる
15.1.4
15.1.1の再帰を使うとfだけでいい
15.1.5
背理法を用いる
動的計画法
1.最適解の構造を特徴づける。
2.最適解の値を再帰的に定義する。
3.ボトムアップ方式で最適解の値を計算する。
4.計算された情報から最適解を計算する。