dynamic programming

dynamic programming is:

when

you find the recurrence reused some value that may require expensive computation

can

memorize these values with a dynamic programming data structure.

recurrence

the recurrence relation on which dynamic programming is useful usually features multiple occurance of \(T(n+c)\) -like stuff.

• fibonaci number - \(T(n) = T(n-1) +T(n-2)\) -> each number is used twice - 2 occurance of \(T(n+c)\) -like stuff

(no term)

dynamic programming data structure

Working buttom-up or top-down

working buttom-up(from \(T_0\) to \(T_n\)) or top-down(from \(T_n\) to whatever others that are used) is almost the same in term of computation complexity and algorithm. As writing memorize and fixed-length(or dynamic-length) array with empty value can be difficult in some programming language.

• top-down is more flexible and easy to write in term of logic/equations, if you get the memoize mechnism right
• buttom-up is generally easier to write in code, but as it is translating recursion to loop, it’s trickier and harder to understand.
• with top-down it is natural that you only compute those values that is required. with buttom-up you may calculate some entries that are not used afterwards while enumerating indexes, and have to write extra conditions if you want to optimize that.
• you need strong recursion with top-down approach. some programming language don’t have that strong recursion to handle top-down approach, In that case, you have to simulate recursion with loop, which is also tricky.

;; this is psudo code in emacs-lisp-like syntax.
;; (memozied index place) return t if position index of place is memoized.
;; (memoize index place value) return value, and memoize value in the index-th position in place
(defun fibonaci (n)
  (if (< n 2)
      1
    (if (memoized n 'fibo) ;; 'fibo stores an 1-D array
        (nth n fibo)
      (memoize
       n 'fibo
       (+ (fibonaci (- n 1))
          (fibonaci (- n 2))
          )
       )
      )
    )

;; 'fibo is a 1-D array
(defun fibonaci (n)
  (loop for i from 1 to n do ;;cl-loop macro syntax
        (if (< i 2)
            (setf (nth i 'fibo) 1) ;; setf can set field of place
          (setf (nth i 'fibo) (+ (nth (- i 1) 'fibo)
                                 (nth (- i 2) 'fibo)
                                 ))
          )
        )
  )