### dynamic programming

####################################
####    Dynamic Programming     ####    (ref) http://www.geeksforgeeks.org/dynamic-programming
####################################

DP is an algorithm paradigm effective for problems that have the following two properties.

(1) overlapping subproblems
(2) optimal substructure

###
###  overlapping subproblems
###

think about a recursive function to compute N'th fibonacci number.
it has lots of overlapping subproblems as below. so the answer to each subproblem can be stored and be looked up.

----------------------------------
def fib(n):
if(n <= 1):
return n
else:
return(fib(n-1) + fib(n-2))
----------------------------------

e.g.
fib(5)
/             \
fib(4)                fib(3)
/      \                /     \
fib(3)      fib(2)         fib(2)    fib(1)
/     \        /    \       /    \
fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
/    \
fib(1) fib(0)

There are two well-established ways to store the answer to each subproblem.

(1) memoization     #  top-down
(2) tabulation      #  bottom-up

###
###   memoization
###

memo = {}
def fib(n, memo):
if n not in memo:
if(n <= 1):
return n
else:
return(fib(n-1, memo) + fib(n-2, memo))
return memo[n]

###
###   tabulation
###

tabu = {}
def fib(n):
tabu = 1
tabu = 1
for i in xrange(2,n+1):
tabu[i] = tabu[i-1] + tabu[i-2]
return tabu[n]

###
###   memoization  VS  tabulation
###

as above, memoization still heavily recursive, so it can accumulate a call stack a lot, lots of memory use, etc.
tabulation needs populating the table every step of the way as it's a bottom up approach. but sometimes you don't need all the intermediate steps, and memoization can potentially get to the answer quicker in such a case.

###
###  optimal substructure
###

suppose a graph problem where you want to travel  S -> G  in the shortest path.

e.g.

-- B --    --- E --
/       \  /        \
S --- A ---V ---- D -- G
\       /  \        /
-- C --    --- F --

you have to pass thru V in any solution, and you can split the whole graph as two shortest-path finding S->V and V->G graph problems.
optimal solution to each subproblem will add up as optimal solution to the entire problem.
(for some problems, only overlapping subproblem property holds, and this optimal substructure property doesn't hold. then DP cannot be used.)

note: identifying a problem as DP problem and building an intuition on its recursive structure are not easy. it takes lots of practice.

###
###  DP exercise: (1) counting ways to sum to N
###

(ref) http://www.geeksforgeeks.org/solve-dynamic-programming-problem/

using 3 numbers {1, 3, 5}, tell the total number of ways to form a number N.
the same number can be used repetitively, and order matter.

e.g.  N=5, then solutions are
1+1+1+1+1
3+1+1
1+3+1
1+1+3

===> so the answer is 3

e.g.
sol_count(5) = 3

let's say sol_count(0) = 1      # because picking an empty set {} will give N=0

(here is how to construct the recursive relation)

sol_count(5) = sol_count(5-1) + sol_count(5-3) + sol_count(5-5)
sol_count(N) = sol_count(N-1) + sol_count(N-3) + sol_count(N-5)

-----------------   # naive recursive version
def sol_count(n):
if(n < 0):
return 0
if(n == 0):
return 1
return sol_count(n-1) + sol_count(n-3) + sol_count(n-5)
----------------

------------------   # memoization version
memo = {}
def sol_count(n):
if(n < 0):
return 0
if(n == 0):
return 1
if n not in memo:
memo[n] = sol_count(n-1) + sol_count(n-3) + sol_count(n-5)
return memo[n]
------------------

------------------  # tabulation version

------------------

###
###  DP exercise (2) : binomial coefficient
###

(ref) http://www.geeksforgeeks.org/dynamic-programming-set-9-binomial-coefficient/

for this problem, you kind of have to know the following setup.

C(n,k) = C(n-1,k-1) + C(n-1,k)
C(n,0) = C(n,n) = 1

---------------------------# naive recursive version

def bc(n,k):
if n == k or k == 0:
return 1
return  bc(n-1,k-1) + bc(n-1,k)

---------------------------

--------------------------# memoization version
memo = {}
def bc(n,k):
if n == k or k == 0:
return 1
if n in memo and k in memo[n]:
return memo[n][k]
else:
if n not in memo:
memo[n] = {}
memo[n][k] = bc(n-1,k-1) + bc(n-1,k)
return memo[n][k]
--------------------------

--------------------------# tabulation version
--------------------------

1. 2017-12-03 23:02:20 |
2. Category : algo
3. Page View: