1289. Minimum Falling Path Sum II¶
题目信息¶
- 题号:
1289
- 难度:
Hard
- 主题:
矩阵、动态规划、行列选择
- 原题:
- 重点:
每行选择一个元素,相邻两行不能选择同一列;最小化所有选中元素之和
题目重述¶
给定 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
解释:只有一个元素可选,不存在相邻行限制。