难度: Hard
给你一个 n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。
非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
示例 1：
输入：grid = [[1,2,3],[4,5,6],[7,8,9]] 输出：13 解释： 所有非零偏移下降路径包括： [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9], [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9] 下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。
示例 2：
输入：grid = [[7]] 输出：7
提示：
n == grid.length == grid[i].length1 <= n <= 200-99 <= grid[i][j] <= 99运行时间: 47 ms
内存: 18.6 MB
class Solution:
def miin(self,nums):
deq = sorted(nums)
return deq[0],deq[1]
def minFallingPathSum(self, grid: List[List[int]]) -> int:
n = len(grid)
if n == 1:
return grid[0][0]
dp = grid[0][:]
a , b = self.miin(grid[0])
for i in range(1,n):
for j in range(n):
if dp[j] != a:
dp[j] = a + grid[i][j]
else:
dp[j] = b + grid[i][j]
a,b = self.miin(dp)
#print(dp,a,b)
return min(dp)
这个问题可以通过动态规划解决。首先，对于第一行，我们可以直接使用输入矩阵的第一行作为初始状态。然后，从第二行开始，我们需要考虑从上一行向下走时的最小成本。为了避免同一列的重复选择，我们需要在更新每一行时知道前一行的最小值和次小值。我们通过自定义函数miin()找出最小值和次小值。在更新当前行的每一列时，如果前一行的这一列的值是最小值，我们选择次小值进行累加，否则选择最小值累加。这样可以确保路径是非零偏移的。最后，通过遍历最后一行的动态规划数组，找到全局最小的下降路径和。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def miin(self, nums):
# 对数组进行排序并返回最小的两个值
deq = sorted(nums)
return deq[0], deq[1]
def minFallingPathSum(self, grid: List[List[int]]) -> int:
n = len(grid)
if n == 1:
return grid[0][0] # 如果只有一行，直接返回该行的唯一元素
dp = grid[0][:] # 初始化dp数组为第一行的值
a, b = self.miin(grid[0]) # 获取第一行的最小值和次小值
for i in range(1, n):
for j in range(n):
if dp[j] == a:
dp[j] = b + grid[i][j] # 如果当前列的值是最小值，选择次小值更新
else:
dp[j] = a + grid[i][j] # 否则选择最小值更新
a, b = self.miin(dp) # 更新最小值和次小值
return min(dp) # 返回最终的最小下降路径和
在函数 `miin` 中，返回的最小值和次小值来自于对整个数组进行排序，而不是限定于某列。因此，这两个值实际上代表了整个数组中的全局最小和次小值。因为我们事先不知道这些值来自哪一列，所以在动态规划的更新过程中，我们会检查当前列的值是否与全局最小值相等，以此来决定是否使用次小值进行更新。这个方法确保了我们不会从相同的列选择两个最小值进行路径的构建。
这种方法的核心在于简化计算和优化性能。考虑每个可能的列组合将会使问题复杂度显著增加，每次更新都需要进行复杂的比较，这在实际应用中可能导致效率低下。通过只考虑最小值和次小值，我们可以有效地减少每次迭代的计算量。此外，最小值和次小值提供了从上一行到当前行的最优和次优的下降路径，这通常足以找到全局最优解。
代码中有一个特定的检查，如果矩阵只有一行（即 `n == 1`），则直接返回该行的第一个元素。这是因为在只有一行的情况下，不存在下降路径的问题，整个行的任何元素都可以视为最终的下降路径和。这个边界情况的处理确保了算法能够正确处理最小规模的输入。
在更新 `dp` 数组时，算法检查当前列的值是否等于前一行的最小值。如果等于，就使用次小值进行更新，这个操作确保了如果当前最小值来源于同一列，我们不会重复选择它，而是选择次小值。这样的策略避免了在相同列中连续选择元素，从而保持了非零偏移的要求。