难度: Medium
现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：
注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。
示例 1:
输入: frame = [[1,3,1],[1,5,1],[4,2,1]]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最高价值的珠宝
提示：
0 < frame.length <= 2000 < frame[0].length <= 200运行时间: 88 ms
内存: 20.3 MB
class Solution:
def maxValue(self, grid: List[List[int]]) -> int:
memo = dict()
def dp(i, j):
if (i, j) in memo:
return memo[(i, j)]
left, up = 0, 0
if j-1 >= 0:
left = dp(i, j-1)
if i-1 >= 0:
up = dp(i-1, j)
memo[(i, j)] = max(left, up) + grid[i][j]
return memo[(i, j)]
return dp(len(grid)-1, len(grid[0])-1)
这个题解采用了动态规划的方法来解决问题。动态规划的思路是通过将原问题分解为相对简单的子问题来求解原问题。在这个问题中，我们定义dp(i, j)为从左上角到达(i, j)位置时能拿到的最高价值的珠宝。那么dp(i, j)可以通过其左边的格子dp(i, j-1)和上边的格子dp(i-1, j)转移而来，转移方程为dp(i, j) = max(dp(i, j-1), dp(i-1, j)) + grid[i][j]。我们使用一个字典memo来存储已经计算过的dp值，以避免重复计算。
时间复杂度: O(m*n)
空间复杂度: O(m*n)
class Solution:
def maxValue(self, grid: List[List[int]]) -> int:
memo = dict()
def dp(i, j):
if (i, j) in memo:
return memo[(i, j)]
left, up = 0, 0
if j-1 >= 0:
left = dp(i, j-1) # 左边的最高价值
if i-1 >= 0:
up = dp(i-1, j) # 上边的最高价值
memo[(i, j)] = max(left, up) + grid[i][j] # 当前位置的最高价值
return memo[(i, j)]
return dp(len(grid)-1, len(grid[0])-1) # 从左上角到右下角的最高价值
在递归版本的动态规划中，确保不会因为递归层数过深导致栈溢出的关键方法是通过使用备忘录（memoization）技术来减少递归的调用次数。在给定问题的实现中，每个状态（即每个格子的最高价值）在第一次计算后就被存储在字典memo中。后续对相同状态的访问将不再触发递归调用，而是直接从字典中取值。这种方法有效地将问题的递归深度限制在格子的总数内，从而避免了由于递归层数过深而导致的栈溢出问题。此外，对于非常大的输入数据，可以考虑使用迭代动态规划或其他非递归方法来避免递归限制。
在动态规划的递归实现中选择使用字典而不是二维数组来存储中间结果的原因主要是灵活性和空间效率。使用字典存储中间结果时，只需要为已经计算过的状态分配空间，这在稀疏数据情况下可以节省大量的内存。此外，字典的键可以是任意可哈希的数据类型，这为状态的表示提供了更大的灵活性。相比之下，二维数组需要预先为所有可能的状态分配空间，无论这些状态是否会被实际访问，这在某些情况下可能会导致内存的浪费。
在`dp(i, j) = max(dp(i, j-1), dp(i-1, j)) + grid[i][j]`的转移方程中，如果grid中某个具体位置的价值非常大，确实会对最终结果产生显著的影响。这是因为动态规划求解的是最大价值路径问题，每个格子的价值直接加入到路径总价值中。因此，任何特别高的格子价值都将直接增加通过该格子的路径的总价值。这种设计是题目本身的特性所致，目的在于找到价值最大的路径。如果需要减少单个格子对总价值的影响，可能需要调整问题的设定或引入额外的规则，例如限制最大值或者引入权重。