矩阵坐标型 | Civilization Museum

type

status

password

date

slug

summary

931. 下降路径最小和

给你一个 n x n 的方形整数数组 matrix，请你找出并返回通过 matrix 的下降路径的最小和。

下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

示例 1：输入：matrix = [[2,1,3],[6,5,4],[7,8,9]] 输出：13 解释：1+5+7=13 1+4+8=13

题解1

我们用 dp(r, c) 表示从任意位置下降到 (r, c) 路径最小和。根据题目的要求，位置(r-1, c-1)，(r-1, c) 和 (r-1, c+1) 三个位置都可以下降到 (r, c) ，因此状态转移方程为：dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+A[i][j]

状态：dp(r, c) 表示从任意位置下降到 (r, c) 路径最小和

边界条件：第一行的任意位置 dp[0][j]=A[0][j]

状态转移方程：dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1])+A[i][j]

自顶向下

自底向上

自底向上-状态压缩

329. 矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1：输入：matrix = [[9,9,4],[6,6,8],[2,1,1]] 输出：4 解释：最长递增路径为 [1, 2, 6, 9]。

题解1

状态：定义dp[i][j]为矩阵第行，第列处的最长路径。

状态转移方程：对于每个单元格，你可以往上，下，左，右四个方向移动，寻找增长的路径。所以状态转移方程是：

边界条件：重点是确定边界条件，如果一个单元格里的 matrix 数字很小，上下左右格子都比它大，此时dp[i][j]=1。

💡

对于一个给定的矩阵其边界的位置是局部最低点（上下左右的格子都比它大），可能不在dp[0][0]，这样写循环语句不方便。所以这种方法适用于自顶向下的动态规划

自顶向下

输出路径

自底向上（不可以）

因为动态规划的边界条件为：如果一个单元格里的 matrix 数字很小，上下左右格子都比它大，此时dp[i][j]=1。

💡

对于一个给定的矩阵其边界（上下左右格子都比它大）可能不在dp[0][0]的位置，这样写循环语句不方便。

Largest Diagonal

给定只包含0、1元素一个2维矩阵，寻找里面的最大单位矩阵。对于右图给定的矩阵，红色部分是最大的单位矩阵。应该输出3.

题解

状态：设dp[i][j] 表示以矩阵第i行、第j列元素为结尾的最大单位矩阵。

边界条件：对于第一行、第一列。如果matrix[i][0]=1，则dp[i][0]=1；如果matrix[0][j]=1，则dp[0][j]=1。

状态转移方程：如上图所示，如果matrix[i][j]=1且绿色部分全为0，则dp[i][j]=dp[i-1][j-1]+1；如果matrix[i][j]=1且黄色部分不全为0，则dp[i][j]=黄色部分的长度；如果matrix[i][j]=0，则dp[i][j]=0

自底向上

221. 最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

示例 1：输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：4

题解1

与Largest Diagonal方式相同

题解2

状态：dp[i,j] 表示以 [i, j] 为右下角，且只包含 1 的正方形的边长最大值。

边界条件：对于第一行或者第一列。如果matrix[i][0]=1，则dp[i][0]=1；如果matrix[0][j]=1，则dp[0][j]=1

状态转移方程：如上图所示，如果matrix[i][j]=0，则dp[i][j]=0；如果matrix[i][j]=1，则dp[i][j]的值取决于 dp[i-1][j-1] 与 matrix[i][j]向上取有多少个连续的1，以及matrix[i][j]向左取有多少个连续的1。

自顶向下

自底向上

自底向上-状态压缩

LC764. 最大加号标志

在一个大小在 (0, 0) 到 (N-1, N-1) 的2D网格 grid 中，除了在 mines 中给出的单元为 0，其他每个单元都是 1。网格中包含 1 的最大的轴对齐加号标志是多少阶？返回加号标志的阶数。如果未找到加号标志，则返回 0。

一个 k 阶由 1 组成的“轴对称”加号标志具有中心网格 grid[x][y] = 1，以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。下面给出 k" 阶“轴对称”加号标志的示例。注意，只有加号标志的所有网格要求为 1，别的网格可能为 0 也可能为 1。

题解1

题目没有给出原始矩阵，我们先脑补一下，设原始矩阵为M。然后，我们用一个dp[N][N][4]数组，来记录每一个点在左上右下四个方向上的臂长。比如，对于点(i,j)，我们有，

dp[i][j][0] -> 向左延伸的臂长 dp[i][j][1] -> 向上延伸的臂长 dp[i][j][2] -> 向右延伸的臂长 dp[i][j][3] -> 向下延伸的臂长

我们这里的臂长包含这个点本身，因此当M[i][j] = 0时任意方向的臂长为0。相反当 M[i][j] = 1时，该点在各个方向的臂长与其周围的四个点有关。

我们通过两次遍历，来构造dp数组。

从左上角开始遍历，计算每个点向左和向上的臂长

从右下角开始遍历，计算每个点向右和向下的臂长一旦我们把dp数组构造好了，对每个点，我们可以很轻松地得到其阶数k，