AcWing 60. 礼物的最大价值
原题链接
中等
作者:
Sei
,
2019-08-30 23:31:49
,
所有人可见
,
阅读 769
python 代码
dp问题,从底向上考虑即可,n^2的时间复杂度,不过这个写的是记忆化搜索的形式
class Solution(object):
def getMaxValue(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
m = len(grid)
if m==0:
return 0
n = len(grid[0])
dp = [[None for j in range(n)]for i in range(m)]
def dfs(i, j):
if i>=m:
return -float('inf')
if j>=n:
return -float('inf')
if dp[i][j]:
return dp[i][j]
if i==m-1 and j==n-1:
dp[i][j] = grid[i][j]
else:
dp[i][j] = max(dfs(i+1, j), dfs(i, j+1))+grid[i][j]
return dp[i][j]
return dfs(0, 0)