タグ: 漸化式

← タグ一覧

• 動的計画法：部分問題を一度だけ解いて指数時間を多項式時間に変える本動的計画法を「部分問題の依存関係が DAG なら位相順に一度ずつ解けばよい」という原理として定式化し、フィボナッチ数列の指数時間再帰が O(n) になる仕組みと、0-1 ナップサック問題の漸化式・O(nW) 表計算・解の復元を証明付きで示す。情報科学アルゴリズムとデータ構造学部動的計画法メモ化ナップサック問題最適部分構造漸化式約 43 分