blob: f389b2dfab35dc99b6ca8d981414f7f35ad24457 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
def get_maxgold(gold, m, n):
goldTable = [[0 for i in range(n)]
for j in range(m)]
for col in range(n-1, -1, -1):
for row in range(m):
if (col == n-1):
right = 0
else:
right = goldTable[row][col+1]
if (row == 0 or col == n-1):
right_up = 0
else:
right_up = goldTable[row-1][col+1]
if (row == m-1 or col == n-1):
right_down = 0
else:
right_down = goldTable[row+1][col+1]
goldTable[row][col] = gold[row][col] + max(right, right_up, right_down)
res = goldTable[0][0]
for i in range(1, m):
res = max(res, goldTable[i][0])
return res
|
