Dynamic programming

[-ordi-]

Hei,

I tried to find "dynamic programming" algorithms in Python.

If anyone has examples of what it means a dynamic programming, it's would be nice.

(Please not post Wikipedia links).

Google -> c++, java and other, not Python.

Thanks!

[TrustyTony]

Here in this old thread is my code for example for the dynamic programming algorithm for lcs (longest common substring). The link points to version were I only keep one row of record, but original algorithm was indexing normal array.

[-ordi-]

Find that, is dynamic programming?

from itertools import product

n = 21
 
coins = [11, 10, 1]                        # Coin denominations.
sol = {0 : 0}                              # Initial solution array.
k = 0                                      # Initial coin count.
while not n in sol:
   k += 1                                  # Increment coin count.
   for v, m in product(sol.keys(), coins): # For each child,
       print v, m
       if v + m > alvo:                    # Skip large solutions.
           continue
       if not v + m in sol:                # If solution is new,
           sol[v + m] = k                  # append solution.
 
# Print solution
print sol[n] 

print sol # {0: 0, 1: 1, 2: 2, 10: 1, 11: 1, 12: 2, 20: 2, 21: 2}

#for v, m in product(sol.keys(), coins):
  #print v, m

[-ordi-]

Hei, enybody knows where I find a traveling salesman algorithm? Or anybody is implementing this thanks!

[richieking]

This is even a basic one. Python can do almost everything you want to do.
:)