top of page

Dynamic Programming Examples

1. Maximum Value Contiguous Subsequence

   

Problem: for an array A[1..n], find the maximum continguous subarray A[i:j] (where i=>0 and j <=n) such that the sum from i to j is greater than any other subarray of A[1..n]  

​

Solution (Python):

​

  1. def M(A,j):

  2.         V = [0] * (j+1)

  3.         V[0] = max(A[0],0)

  4.  

  5.         for i in range(1,len(A),1):

  6.                 V[i]= max(V[i-1]+A[i],A[i])

  7.         return max(V)

  8.  

  9. A = [0,1,2,3,-1,77,22,100,-44,-55]

  10. j = len(A)

  11. print M(A,j)

2. Making Change:  

​

Solved. However, the solution conflicts with an existing homework problem. 

​

3. Longest Increasing Subsequence

​

Problem: for an array A[1..n], find the longest subsequence (not necessarily contiguous) such that all elements in the subsequence are increasing from the previous.   

​

Solution (Python):

​

  1. def M(A):

  2.         V = [0]*(len(A)+1)

  3.  

  4.         for i in range(0,len(A),1):

  5.                 for j in range(0,i+1,1):

  6.                         if (A[i] > A[j]):

  7.                                 V[i]=max(V[i],V[j]+1)

  8.         return max(V)

  9.  

  10. A = [1,2,44,3,5,100,220,6]

  11. print M(A)

​

4. Integer Knapsack Problem (Duplicate Items Forbidden)

 

Problem: Given a knapsack of capacity=c and an array of items of sizes = S and an array of values=V, what is the optimal (highest value) solution of items that can be placed in the knapsack without exceeding the capacity. 

​

Solution (Python): 

  1. def M(S,V,c):

  2.         C = [[0]*(c+1) for i in xrange(len(S)+1)]

  3.         for i in range(0,len(S),1):

  4.                 for j in range(0,c+1,1):

  5.                         if (i==0):

  6.                                 C[0][j]=max(V[0],0)

  7.                         else:

  8.                                 if ((j-S[i]) >= 0):

  9.                                         C[i][j]=max(C[i-1][j],C[i-1][j-S[i]]+V[i])

  10.                                 else:

  11.                                         C[i][j]=max(C[i-1][j],V[i])

  12.         return C[len(S)-1][c]

  13.  

  14. S = [1,2,3,4,5]

  15. V = [22,5,40,3,2]

  16. c = 4

  17. print M(S,V,c)

​

5. Edit Distance

​

Problem: Given two strings A[1..m], B[1..n], what are the minimum number of operations (delete, insert, replace) that can be performed on the strings to transform A into B.

​

Solution (Python):

  1. def M(X,Y):

  2.         X = "!"+X # place a terminator character to ignore at front of string

  3.         Y = "!"+Y # place a terminator character to ignore at front of string

  4.         m = len(X)-1

  5.         n = len(Y)-1

  6.         T = [[float('inf')]*(len(Y)+1) for i in xrange(len(X)+1)]

  7.  

  8.         for i in range(0,m,1):

  9.                 for j in range(0,n,1):

  10.                         if (i==0 or j==0):

  11.                                 T[i][j]=0

  12.                         else:

  13.                                 if (X[i]!=Y[j]): val = T[i-1][j-1]+1

  14.                                 else: val = T[i-1][j-1]

  15.                                 T[i][j] = min(T[i-1][j]+1,T[i][j-1]+1,val)

  16.         return T[m-1][n-1]

  17.  

  18. X = "ALGOSCS505"

  19. Y = "ALGORITHMS"

  20. print M(X,Y)

 

bottom of page