## 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 =  * (j+1)

3.         V = max(A,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 = *(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.

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

2.         C = [*(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[j]=max(V,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)