Date
Aug 10, 2023
need_review
need_review
type
undo
undo
难度
困难
给你一个
n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。非零偏移下降路径 定义为：从
grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。示例 1：
示例 2：
提示：
n == grid.length == grid[i].length
1 <= n <= 200
99 <= grid[i][j] <= 99
解法1
递归 bfs 返回时找到最小的和
回溯的时候, 记得加上当前值, 时间复杂度为, 空间复杂度为
超时
解法2
使用动态规划, 状态矩阵记录加法结果. 时间复杂度为, 空间复杂度为
