egg drop problem
#A Dynamic Programming based Python Program for the Egg Dropping Puzzle
INT_MAX = 32767
#Function to get minimum number of trials needed in worst
#case with n eggs and k floors
def eggDrop(n, k):
# A 2D table where entry eggFloor[i][j] will represent minimum
#number of trials needed for i eggs and j floors.
eggFloor = [[0 for x in range(k + 1)] for x in range(n + 1)]
#We need one trial for one floor and0 trials for 0 floors
for i in range(1, n + 1):
eggFloor[i][1] = 1
eggFloor[i][0] = 0
#We always need j trials for one egg and j floors.
for j in range(1, k + 1):
eggFloor[1][j] = j
#Fill rest of the entries in table using optimal substructure
#property
for i in range(2, n + 1):
for j in range(2, k + 1):
eggFloor[i][j] = INT_MAX
for x in range(1, j + 1):
res = 1 + max(eggFloor[i-1][x-1], eggFloor[i][j-x])
if res < eggFloor[i][j]:
eggFloor[i][j] = res
#eggFloor[n][k] holds the result
return eggFloor[n][k]#Driver program to test to pront printDups
n = 2
k = 36
print("Minimum number of trials in worst case with" + str(n) + "eggs and "
+ str(k) + " floors is " + str(eggDrop(n, k)))
LCS -
def lcs(X , Y):
# find the length of the strings
m = len(X)
n = len(Y)
#declaring the array for storing the dp values
L = [[None]*(n+1) for i in xrange(m+1)]
"""Following steps build L[m+1][n+1] in bottom up fashion
Note: L[i][j] contains length of LCS of X[0..i-1]
and Y[0..j-1]"""
for i in range(m+1):
for j in range(n+1):
if i == 0 or j == 0 :
L[i][j] = 0
elif X[i-1] == Y[j-1]:
L[i][j] = L[i-1][j-1]+1
else:
L[i][j] = max(L[i-1][j] , L[i][j-1])
#L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1]
return L[m][n]#end of function lcs
#Driver program to test the above function
X = "AGGTAB"
Y = "GXTXAYB"
print "Length of LCS is ", lcs(X, Y)