8.27 网格memo
lc329
计算矩阵中最长递增路径长度
尝试从矩阵每个位置出发，int dfs() 往上下左右四个方向找严格递增的路径
ret=max(ret,dfs(x,y)+1);
return memo[i][j]=ret;
返回所有路径里的最长长度
class Solution
{
public:
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int m,n;
vector<vector<int>> memo;
vector<vector<int>> matrix;
int longestIncreasingPath(vector<vector<int>>& matrix)
{
this->matrix=matrix;
m=matrix.size();
n=matrix[0].size();
int cnt=0;
memo.resize(m,vector<int>(n,0));
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
cnt=max(cnt,dfs(i,j));
}
}
return cnt;
}
int dfs(int i,int j)
{
if(memo[i][j]) return memo[i][j];
int ret=1; //init
for(int k=0;k<4;k++)
{
int x=i+dx[k],y=j+dy[k];
if(x>=0 && x<m && y>=0 && y<n
&& matrix[x][y]>matrix[i][j])
{
ret=max(ret,dfs(x,y)+1);
}
}
return memo[i][j]=ret;
}
};
lc3459
int dfs 沿着某个方向一步步探路，符合规则（值对、没越界）就接着走，还能处理 “转一次弯” 的情况
同时用 memo 避免重复计算，(memo[i][j][k]: 从 (i,j) 位置往第 k 个方向走的最长有效长度)
1. 整体思路
代码要在一个由 0、1、2 组成的二维矩阵里，找符合 “V 形对角线段” 规则的最长线段。
核心逻辑：从每个值为 1 的位置出发，沿着四个可能的对角方向（比如↘、↙、↖、↗ 这类斜线方向）去探索，按照 2、0、2、0…… 的序列模式走，还能最多右转一次 90 度弯，最后找出所有情况里最长的线段长度。
class Solution {
static constexpr int DIRS[4][2] = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
public:
int lenOfVDiagonal(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector memo(m, vector<array<int, 4>>(n));
auto dfs = [&](this auto&& dfs, int i, int j, int k, bool can_turn, int target) -> int
{
i += DIRS[k][0];
j += DIRS[k][1];
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != target) {
return 0;
}
// 只在 can_turn=false 时读取和写入 memo
if (!can_turn && memo[i][j][k]) {
return memo[i][j][k];
}
int res = dfs(i, j, k, can_turn, 2 - target) + 1; //延此方向往下走
if (!can_turn) {
return memo[i][j][k] = res;
}
int maxs[4] = {m - i, j + 1, i + 1, n - j}; // 理论最大值（走到底）
k = (k + 1) % 4;//顺时针
// 优化二：如果理论最大值没有超过 res，那么不递归
if (min(maxs[k], maxs[(k + 3) % 4]) > res) {
res = max(res, dfs(i, j, k, false, 2 - target) + 1); //尝试转后，还是维护最大
}
return res;
};
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != 1)
continue;
int maxs[4] = {m - i, j + 1, i + 1, n - j}; // 理论最大值（走到底）
for (int k = 0; k < 4; k++) {
// 优化一：如果理论最大值没有超过 ans，那么不递归
if (maxs[k] > ans) {
ans = max(ans, dfs(i, j, k, true, 2) + 1);
}
}
}
}
return ans;
}
};
2. 解释
（1）方向定义
static constexpr int DIRS[4][2] = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
预先定义好的 4 种对角移动方向
（2）记忆化搜索（ memo 数组）
vector memo(m, vector<array<int, 4>>(n));
//memo 是用来 缓存已经计算过的结果 ，避免重复计算。比如从 (i,j) 位置往第 k 个方向走的最长有效长度，算过一次就存起来，下次再碰到就直接用，能提升效率。
（3）深度优先搜索（ dfs 函数）
auto dfs = [&](this auto&& dfs, int i, int j, int k, bool can_turn, int target) -> int {
// 先沿着当前方向走一步，更新坐标
i += DIRS[k][0];
j += DIRS[k][1];
if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != target) {
return 0;
}
// 如果还不能转弯（can_turn=false），看看缓存里有没有结果，有的话直接返回
if (!can_turn && memo[i][j][k]) {
return memo[i][j][k];
}
// 能走到这，说明当前格子有效，接着往下一步找，递归调用 dfs，同时切换下一个要找的 target（2 变 0，0 变 2 ）
int res = dfs(i, j, k, can_turn, 2 - target) + 1;
// 如果还不能转弯，就把当前算出来的结果存到 memo 里，方便后续复用
if (!can_turn) {
return memo[i][j][k] = res;
}
// 下面是处理 “可以转弯” 的情况
int maxs[4] = {m - i, j + 1, i + 1, n - j};
// 切换方向（右转 90 度，对应 k = (k + 1) % 4 ）
k = (k + 1) % 4;
// 优化：如果理论上转完弯能走的长度，还没当前 res 长，就不递归了，省点时间
if (min(maxs[k], maxs[(k + 3) % 4]) > res) {
// 转弯后，不能再转了（can_turn 设为 false ），递归计算新方向的长度，然后和当前 res 比，取大的
res = max(res, dfs(i, j, k, false, 2 - target) + 1);
}
return res;
};
简单说
dfs 沿着某个方向一步步探路，符合规则（值对、没越界）就接着走，还能处理 “转一次弯” 的情况
同时用 memo 避免重复计算，(memo[i][j][k]: 从 (i,j) 位置往第 k 个方向走的最长有效长度)
（4）主逻辑遍历
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 只从值为 1 的位置开始找，因为题目说线段从 1 开始
if (grid[i][j] != 1) {
continue;
}
// 计算从 (i,j) 出发，四个方向理论上能走的最大长度（走到边界的长度）
int maxs[4] = {m - i, j + 1, i + 1, n - j};
for (int k = 0; k < 4; k++)
{
// 优化：如果理论长度都没当前 ans 大，没必要递归，跳过
if (maxs[k] > ans) {
// 从 (i,j) 出发，第 k 个方向，允许转弯（can_turn=true），第一个要找的 target 是 2
ans = max(ans, dfs(i, j, k, true, 2) + 1);
}
}
}
}
return ans;
遍历整个矩阵 ，找到所有值为 1 的位置，然后对每个 1 的位置，尝试四个对角方向出发去探索最长 V 形线段，不断更新 ans （记录全局最长长度 ）
auto dfs = [&](this auto&& dfs, int i, int j, int k, bool can_turn, int target) -> int
{
// ... 函数体
};
递归lambda的写法，显式捕获当前类的 this 指针，在 Lambda 内部访问类的成员。
用function包装写也行