Solution to problem on slide 5:
# this is a dp problem. For each node calculate the minimum cost to each node in the next row
y = len(grid)
x = len(grid[0])
minvalprev = grid[0] #cost of first row
for i in range(y-1):
minval = [1e10]*x
for j1 in range(x):
val = grid[i][j1]
for j2 in range(x):
#minimum cost of each column in the next row updated by the current node
minval[j2] = min(minval[j2],
minvalprev[j1]+moveCost[val][j2] +grid[i+1][j2])
minvalprev=minval
return min(minval)
Solution to problem on slide 6 (HW):
The standard recursive solution, if p and q exist, then their children and their values must be equal.
def isSameTree(self, p, q):
if p and q:
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
return p is q