メモ化は 1 つの方法であり、別の方法は別のデータ表現を使用することです。
行列、またはベクトルのベクトルとして表されるグリッドを使用しました。
次に、一番上の行の値を 1 に設定します (上端にのみパスがあるためです。
その後、次の行または行の最初の行は 1 で、2 番目の行は 1 つ上の列のエントリの値に、その行の前のエントリまたは値を加えたものです。
行の各ポイントに対して再帰し、次に各行に対して再帰します。
答えは、再帰が完了したときの最後の行の最後のポイントです。
3x3 グリッドの場合
1 1 1
1 2 3
1 3 6
6
キーが非常に接近している場合 (連続、またはそれに近い場合)、ベクトル表現はハッシュよりもパフォーマンスが高くなります。
(define (make-lattice-point-square n)
(let ((lps (make-vector (+ n 1))))
(let loop ((i 0))
(if (> i n)
lps
(begin
(vector-set! lps i (make-vector (+ n 1)))
(loop (++ i)))))))
(define (lattice-ref lat x y)
;; where x is row, y is column thought it's not really important
(vector-ref (vector-ref lat y) x))
(define (lattice-set! lat x y value)
(vector-set! (vector-ref lat y) x value))
;; paths through a point are equal the the paths through the above point,
;; plus the paths through the left, those along the top and left edges
;; only have one possible path through them
(define (ways-exit-lattice n)
(let ((lps (make-lattice-point-square n)))
(letrec
((helper
(lambda (x y)
(if (or (= x 0) (= y 0))
(lattice-set! lps x y 1)
(lattice-set! lps x y
(+ (lattice-ref lps (- x 1) y)
(lattice-ref lps x (- y 1)))))))
(lattice-walker
(lambda (x y)
(cond ((and (= x n) (= y n))
(begin (helper x y) (lattice-ref lps x y)))
((= y n)
(begin
(helper x y)
(lattice-walker (++ x) 0)))
(else
(begin
(helper x y)
(lattice-walker x (++ y))))))))
(lattice-walker 0 0))))
latice-walker へのすべての呼び出しがテール コールであることに注意してください。
RSR5準拠のスキームを使用