Dynamic Programing on Racket

user_10010623 0
Viewed 218

So I have an exercise where I should count the ways of climbing a ladder with n amount of steps, with the following restriction: You can only go up by 1, 3 or 5 steps.

The way I could solve the problem was with this code.

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

But the problem now is that it is too difficult to get the result, you have to do a lot of calculations. Is it possible to optimize this on the racket? What would the code be like? If I could save the previous 2 results and add it up, it would work better, but I don't know how.

racket dynamic-programming scheme lisp algorithm
1 Answers

The trick with dynamic programming is to store previous values that have already been computed, in this way we don't have to redo expensive recursive calls. Usually we store the values in an array, a matrix or a hash table - but for this case we can simply use a bunch of parameters and tail recursion. This works, and it's pretty fast!

(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))))))

For example:

(climb 100)
=> 20285172757012753619
user_2013590
Related