Schemeで動的計画法 - Qiita

Schemeで、メモ化再帰でない動的計画法によるアルゴリズムの記述をしてみました。 例題に用いたのは、ProjectEuler #18です。 解答プログラムはgithubにて公開しています。 Given: 入力は２次元配列dとして表現される。配列dはl×l要素。 配列dはSRFI-25: Multi-dimensional Array Primitives として表現される。 １．定義 関数opt(i,j) を定義する。 関数opt(i,j) は地点(i,j)から下端まで移動するときの数値の和の最大値。 ２．基底 実装は、SRFI-42 のdo-ec により実現。 i を下端、すなわちl-1 に固定し、j を範囲[0,l) で動かす。 この範囲でのopt(i,j) の値は、d(i,j) の値を複写する。 下端では、その地点の数値が和の最大値。 すなわち、opt(l-1,j)=d(l-1,j