Dynamic Programming

• Dynamic programming can be applied when the recursive calls are basically computing a value, and not doing some operations. Fibonacci series, combinatorial, knapsack problem.
• Negative examples: quicksort, merge sort.
• Towers of Hanoi: can be solved by dynamic programming but it requires a lot of extra memory space.
• General idea: store values computed by recursive calls that could be repeated in the computation.

Bottom-Up DP

• The computation starts from the base cases and follows an iterative process going increasingly in the parameter values.
• Example: Fibonacci series. F(n) = F(n-1) + F(n-2), F(0)=1, F(1)=1
• We store F(n) in an array. We start from 2 going up to n. At every iteration we store the value in a new element of the array.
• It can be optimized based on the fact that we only need the last two values we computed.

Fibonacci

(defun fib1 (n)
  (if (<= n 1) 1
    (+ (fib1 (- n 1))
       (fib1 (- n 2)))))

(defun fib (n)
  (let ((f0 1) (f1 1) (f 1) (i 2))
    (while (<= i n)
      (setq f (+ f0 f1) f0 f1 f1 f i (+ i 1)))
    f))

(fib 5) ; 8

Top-Down DP

• The structure of the function closely follows that of the original recursive function.
• We store the result of every recursive call in an array initialized to some nil value.
• Every time we encounter a new function call, we check the corresponding element in the array.
• If the value is not nil, we call the function recursively.
• If the value is nil, we use it instead of the recursive call.

Combinations
C(n, m) = n! / (m! (n-m)! )
C(n, m) = C(n-1, m) + C(n-1, m-1)

(defun comb (n m)
  (cond
   ((= n m) 1)
   ((= m 0) 1)
   ((= m 1) n)
   (t (+ (comb (- n 1) m)
         (comb (- n 1) (- m 1))))))
(comb 3 2) ; 3
(comb 5 2) ; 10

Improved version with DP:

(defun el10 (n m)
  (+ (* n 10) m)) ; 10*n+m

(setq C (make-vector 200 nil))

(defun comb1 (n m)
  (let ((res 0))
    (if (setq res (elt C (el10 n m))) res
      (setq res
            (cond
             ((= n m) 1)
             ((= m 0) 0)
             ((= m 1) n)
             (t (+ (comb1 (- n 1) m)
                   (comb1 (- n 1) 
                          (- m 1))))))
      (aset C (el10 n m) res))))

(comb1 7 3) ; 35
(comb1 10 5) ; 252

Knapsack Problem

• A thief robbing a safe finds N types of items of various size and value, but only has a knapsack of capacity M to carry the goods.
• Question: how does the thief optimize the total value of the stolen items?
• Example:

  Item	A	B	C	D	E
  Size	3	4	7	8	9
  Value	4	5	10	11	13

• A knapsack of size 17 can have 5 A's with a value of 20 or a D and an E for a total value of 24.

General Solution
For every possible object O_i(size_i, value_i) of size less or equal to the capacity of the knapsack:

• Find the best value res_i that you can put in a knapsack of capacity equal to the original M minus size_i.
• Add value_i to this quantity.
• Find the item that gives you the best combined value res_i + value_i.
• The function requires a loop of recursive calls.

Simple Recursive Solution

(defun knapsack (S Olist)
  "Simple recursive knapsack."
  (if (= S 0) 0
    (let ((maxval 0) (res 0) (size 0) 
          (val 0))
      (dolist (c Olist maxval)
        (setq size (car c) val (cdr c))
        (cond ((>= S size)
               (setq res (knapsack 
                          (- S size) Olist))
               (if (> (+ res val) maxval)
                   (setq maxval 
                         (+ res val))))))))
(setq Obj-list '((3 . 4) (4 . 5) (7 . 10) 
                 (8 . 11) (9 . 13)))
(knapsack 17 Obj-list) ; 24

Solution with DP

(setq store (make-vector 20 nil))

(defun knapsack1 (S Olist)
  "Recursive knapsack with dynamic programming."
  (let ((maxval 0) (res 0) (size 0) (val 0))
    (cond ((setq res (elt store S)) res)
          ((= S 0) 0)
          (t
           (dolist (c Olist maxval)
             (setq size (car c) val (cdr c))
             (cond ((>= S size)
                    (setq res (knapsack1 
                               (- S size) Olist))
                    (if (> (+ res val) maxval)
                        (setq maxval (+ res
                                        val))))))
           (aset store S maxval)))))

(knapsack1 17 Obj-list); 24