1289. Minimum Falling Path Sum II

题目信息

题号:

1289

难度:

Hard

主题:

矩阵、动态规划、行列选择

原题:

LeetCode 1289

重点:

每行选择一个元素,相邻两行不能选择同一列;最小化所有选中元素之和

题目重述

给定 n x n 整数矩阵 grid。需要从每一行恰好选择一个元素,并保证相邻两行所选元素不位于同一列。

请返回所有合法选择中,选中元素总和的最小值。

1 <= n <= 200,-99 <= grid[i][j] <= 99。

自建示例

两行矩阵必须选择不同列:

输入:grid = [[1,2],[3,4]]
输出:5
解释:可以选择第一行的 1 和第二行的 4,或选择 2 和 3,两种方案总和都是 5。

单行矩阵直接选择该行最小值:

输入:grid = [[-5]]
输出:-5
解释:只有一个元素可选,不存在相邻行限制。