0931. Minimum Falling Path Sum

题目信息

题号:

0931

难度:

Medium

主题:

方阵、下降路径、最小元素和

原题:

LeetCode 0931

重点:

路径从第一行任意列开始并在每一行选择一个元素;下一行只能走到同列或相邻列,最终必须到达最后一行

题目重述

给定 n x n 整数矩阵 matrix。一条下降路径从第一行的任意元素开始,此后每进入下一行,列下标只能保持不变、减一或加一,并且始终不能越过矩阵边界。

路径必须恰好在每一行选择一个元素,直到最后一行。请返回所有下降路径中元素总和的最小值。

1 <= n <= 100,-100 <= matrix[i][j] <= 100。

自建示例

向左下方移动得到更小和:

输入:matrix = [[2,1],[3,4]]
输出:4
解释:从第一行的 1 开始,可以移动到下一行左侧的 3,总和为 4;其他路径的和都不小于 4。

矩阵只有一个格子:

输入:matrix = [[-5]]
输出:-5
解释:唯一的下降路径只包含这个格子,因此最小路径和就是 -5。