LC-931 下降路径最小和（记忆化搜索 ==＞ 动态规划）

**LC-931: 下降路径最小和**

**题目描述**

给定一个由整数组成的二维数组 `grid`，其中每个元素都有一个值。我们需要找到从左上角到右下角的路径中，所有数字之和最小的路径。

**记忆化搜索**

首先，我们可以使用记忆化搜索来解决这个问题。记忆化搜索是一种优化的递归方法，它通过存储已经计算过的结果来避免重复计算，从而提高效率。

def minFallingPathSum(grid):
 memo = {}

 def dfs(i, j):
 if (i, j) in memo:
 return memo[(i, j)]
 # Base case: 如果到达右下角，直接返回当前值 if i == len(grid) -1 and j == len(grid[0]) -1:
 return grid[i][j]
 # 递归计算左、上和左上三个方向的最小值 left = dfs(i, j +1)
 top = dfs(i +1, j)
 topLeft = dfs(i +1, j +1)

 # 将当前值加上最小值，存储结果 memo[(i, j)] = grid[i][j] + min(left, top, topLeft)
 return memo[(i, j)]

 # 从左上角开始递归计算 return dfs(0,0)

def minFallingPathSum(grid):
 rows = len(grid)
 cols = len(grid[0])

 # 初始化第一行和第二行 dp = [[0] * cols for _ in range(rows)]
 dp[0][0] = grid[0][0]
 # 计算第一行 for j in range(1, cols):
 dp[0][j] = grid[0][j] + dp[0][j -1]

 # 计算第二行 for i in range(1, rows):
 dp[i][0] = grid[i][0] + dp[i -1][0]
 # 计算剩余部分 for i in range(1, rows):
 for j in range(1, cols):
 dp[i][j] = grid[i][j] + min(dp[i -1][j], dp[i][j -1], dp[i -1][j -1])

 # 返回最小值 return min(dp[-1])