【动态规划】【矩阵】C++算法329矩阵中的最长递增路径

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

题目

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

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

示例 1：

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]

输出：4

解释：最长递增路径为 [1, 2, 6, 9]。

示例 2：

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]

输出：4

解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

示例 3：

输入：matrix = [[1]]

输出：1

提示：

m == matrix.length

n == matrix[i].length

1 <= m, n <= 200

0 <= matrix[i][j] <= 2³¹ – 1

动态规划

时间复杂度: O(nmlog(nm))。

一，将行列压缩成一维。m_c*r+c。

二，建立图论的临接表。两个节点4连接，值小的指向值大的。

三，从值大的到值小的动态规划。

动态规划的细节，方便检查

注意：最小值不一定是最大长度。比如：

1只能1->9

2可以2->3->4

代码

核心代码

class CEnumGridEdge
{
public:
	void Init()
	{
		for (int r = 0; r < m_r; r++)
		{
			for (int c = 0; c < m_c; c++)
			{
				Move(r, c, r + 1, c);
				Move(r, c, r - 1, c);
				Move(r, c, r, c + 1);
				Move(r, c, r, c - 1);
			}
		}
	}
protected:
	CEnumGridEdge(int r, int c) :m_r(r), m_c(c)
	{
		
	}
	void Move(int preR, int preC, int r, int c)
	{
		if ((r = m_r))
		{
			return;
		}
		if ((c = m_c))

		{
			return;
		}
		OnEnumEdge(preR, preC, r, c);
	};
	virtual void OnEnumEdge(int preR, int preC, int r, int c) = 0;
const int m_r, m_c;
};

class CMatToNeibo : public CEnumGridEdge
{
public:
	CMatToNeibo(const vector<vector>& matrix) :CEnumGridEdge(matrix.size(), matrix[0].size()), m_mat(matrix), m_NodeCount(m_r* m_c), m_vNeiBo(m_NodeCount)
	{
		for (int r = 0; r < m_r; r++)
		{
			for (int c = 0; c < m_c; c++)
			{
				m_mValueToIndex.emplace(matrix[r][c], m_c * r + c);
			}
		}
	}
	int Do()
	{
		Init();
		vector dp(m_NodeCount);
		for (const auto& [_tmp, inx] : m_mValueToIndex)
		{
			int iMax = 0;
			for (const auto& next : m_vNeiBo[inx])
			{
				iMax = max(iMax, dp[next]);
			}
			dp[inx] = iMax + 1;
		}
		return *std::max_element(dp.begin(),dp.end());
	}
	const int m_NodeCount;
	vector<vector> m_vNeiBo;
	const vector<vector>& m_mat;
	std::multimap<int, int, greater> m_mValueToIndex;
protected:
	virtual void OnEnumEdge(int preR, int preC, int r, int c)
	{
		if (m_mat[preR][preC] < m_mat[r][c])
		{
			m_vNeiBo[m_c * preR + preC].emplace_back(m_c * r + c);
		}
	}
};

class Solution {
public:
	int longestIncreasingPath(vector<vector>& matrix) {
		CMatToNeibo mn(matrix);
		return mn.Do();
	}
};

2023年1月

class Solution {

public:

int longestIncreasingPath(vector& matrix) {

m_r = matrix.size();

m_c = matrix[0].size();

m_dp.assign(m_r, vector(m_c, -1));

std::map<int,vector<pair>> mVRC;

for (int r = 0; r < m_r; r++)

{

for (int c = 0; c < m_c; c++)

{

mVRC[matrix[r][c]].emplace_back(r, c);

}

}

for (auto& it : mVRC)

{

for (auto& rc : it.second)

{

m_dp[rc.first][rc.second] = Test(matrix, rc.first, rc.second);

}

}

int iMax = 0;

for (int r = 0; r < m_r; r++)

{

for (int c = 0; c < m_c; c++)

{

iMax = max(iMax, m_dp[r][c]);

}

}

return iMax;

}

int Test(const vector& matrix,int r, int c)

{

int iMax = 0;

if ((r > 0) && (matrix[r][c] > matrix[r – 1][c]))

{

iMax = max(iMax,m_dp[r-1][c] );

}

if ((r +1 matrix[r + 1][c]))

{

iMax = max(iMax, m_dp[r + 1][c]);

}

if ((c > 0) && (matrix[r][c] > matrix[r][c-1]))

{

iMax = max(iMax, m_dp[r][c-1]);

}

if ((c + 1 matrix[r][c + 1]))

{

iMax = max(iMax, m_dp[r][c + 1]);

}

return iMax + 1;

}

int m_r;

int m_c;

vector m_dp;

};

2023年8月

class Solution {

public:

int longestIncreasingPath(vector& matrix) {

m_r = matrix.size();

m_c = matrix.front().size();

m_iMaskNum = m_r * m_c;

//生成邻接表

vector vNeiBo(m_iMaskNum);

vector vInDeg(m_iMaskNum);

for (int r = 0; r < m_r; r++)

{

for (int c = 0; c < m_c; c++)

{

auto Add = [this,&matrix, &vNeiBo,&vInDeg](int curMask, int curValue, int r, int c)

{

if ((r = m_r))

{

return;

}

if ((c = m_c))

{

return;

}

if (curValue > matrix[r][c])

{

vNeiBo[r * m_c + c].emplace_back(curMask);

vInDeg[curMask]++;

}

};

Add(r * m_c + c, matrix[r][c], r + 1, c);

Add(r * m_c + c, matrix[r][c], r – 1, c);

Add(r * m_c + c, matrix[r][c], r, c + 1);

Add(r * m_c + c, matrix[r][c], r, c – 1);

}

}

//top排序

queue que;

vector vLen(m_iMaskNum, 0);

for (int i = 0; i < m_iMaskNum; i++)

{

if (0 == vInDeg[i])

{

que.emplace(i);

vLen[i] = 1;

}

}

while (que.size())

{

const int cur = que.front();

que.pop();

for (const auto& next : vNeiBo[cur])

{

if (–vInDeg[next] == 0)

{

vLen[next] = vLen[cur] + 1;

que.emplace(next);

}

}

}

return *std::max_element(vLen.begin(), vLen.end());

}

int m_r;

int m_c;

int m_iMaskNum;

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者 操作系统：win10 开发环境： VS2022 **C+

+17**

如无特殊说明，本算法用**C++**实现。