Racket 上的动态编程

Question

所以我有一个练习，我应该计算爬 n 步梯子的方式，有以下限制：你只能上 1、3 或 5 步。

我解决问题的方法是使用这段代码。

(define (climb n)
   (cond [(< n 0) 0]   
         [(<= n 2) 1]
         [(= n 3) 2]
         [(> n 1) (+ (climb (- n 1)) (climb (- n 3)) (climb (- n 5)))]
   )
)

但现在的问题是求出结果太难了，得做很多计算。有没有可能在球拍上优化这个？代码会是什么样的？如果我能把之前的2个结果保存下来再相加，效果会更好，但我不知道如何。

Answer 1

动态规划的诀窍是存储已经计算过的先前值，这样我们就不必重做昂贵的递归调用。通常我们将值存储在数组、矩阵或散列中 table - 但对于这种情况，我们可以简单地使用一堆参数和尾递归。这有效，而且速度非常快！

(define (climb n)
  (if (negative? n)
      0
      (let loop ([n n] [a 1] [b 1] [c 1] [d 2] [e 3] [f 5])
        (if (zero? n)
            a
            (loop (sub1 n) b c d e f (+ a b c d e))))))

例如：

(climb 100)
=> 20285172757012753619

Racket 上的动态编程

Dynamic Programing on Racket

lisp

algorithm

scheme

dynamic-programming

racket