動的計画法の例題です。連鎖行列積をやります。アルゴリズムの勉強と実装をします。 連鎖行列積 厳しい名前がついていますが、やることは行列の積の計算順序の決定です。 与えられたn個の行列の連鎖の積を計算しますが、計算結果には興味がありません。見つ…

動的計画法の例題です。最長共通部分列を実装します。 目標 最長共通部分列を実装する 最長共通部分列 ２つの列X、Yがあるとします。XとYの共通部分列のうち、最長のものを最長共通部分列（Longest Common Subsequence, LCS）と言います。列は数列など色々な…

動的計画法の例題としておなじみのフィボナッチ数列を実装します。 目標 動的計画法の基本的なアイディアを理解する。 フィボナッチ数列 次のように定義されます。 いかにも再帰関数で書けそうです。 素朴な再帰関数による実装 nを入力として与えると、フィ…