【动态规划】【map】【C++算法】1289. 下降路径最小和 II

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总

map

LeetCode1289. 下降路径最小和 II

给你一个 n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。

非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。

示例 1：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]]

输出：13

解释：

所有非零偏移下降路径包括：

[1,5,9], [1,5,7], [1,6,7], [1,6,8],

[2,4,8], [2,4,9], [2,6,7], [2,6,8],

[3,4,8], [3,4,9], [3,5,7], [3,5,9]

下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。

示例 2：

输入：grid = [[7]]

输出：7

提示：

n == grid.length == grid[i].length

1 <= n <= 200

-99 <= grid[i][j] <= 99

动态规划

动态规划的状态表示

multimap mSumToIndex 的key，各行的最小和,value 列下标。 mSumToIndex不包括当前行，mDp包括当前行。

只需要比较mSumToIndex 最小元素和次小元素。

动态规划的转移方程

各列和mSumToIndex的最小、次小元素结合，最小值为iMin。将iMin和列号放到mDp中。

动态规划的初始值

{0,1} {0,1}

动态规划的填表顺序

依次处理各行。

动态规划的返回值

mSumToIndex.begin().first

map

map可以分成有序(单调)map和无序(哈希)map。还可分成单键map和多键map（允许重复的键）。本文用的是有序、多键。

代码

核心代码

class Solution {
public:
	int minFallingPathSum(vector<vector>& grid) {
		const int n = grid.size();
		if (1 == n)
		{
			return grid[0][0];
		}
		multimap mSumToIndex;
		mSumToIndex.emplace(0, 0);
		mSumToIndex.emplace(0, 1);
		for (const auto& v : grid)
		{
			const auto it = mSumToIndex.begin();
			const auto it1 = next(it);
			multimap mDp;
			for (int i = 0; i < n; i++)
			{
				int iMax = INT_MAX;
				if (it->second != i)
				{
					iMax = min(iMax, it->first + v[i]);
				}
				if (it1->second != i)
				{
					iMax = min(iMax, it1->first + v[i]);
				}
				mDp.emplace(iMax, i);
			}
			mSumToIndex.swap(mDp);
		}
		return mSumToIndex.begin()->first;
	}
};

测试用例

template
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	vector<vector> grid;
	{
		Solution sln;
		grid = { {1,2,3},{4,5,6},{7,8,9} };
		auto res = sln.minFallingPathSum(grid);
		Assert(13, res);
	}

	{
		Solution sln;
		grid = { {7} };
		auto res = sln.minFallingPathSum(grid);
		Assert(7, res);
	}
}

2023年一月版

class Solution {

public:

int minFallingPathSum(vector& grid) {

if (1 == grid.size())

{

return grid[0][0];

}

vector pre = grid[0];

for (int i = 1; i < grid.size(); i++)

{

vector dp(grid.size(), 1000 * 1000 * 1000);

for (int j = 0; j < dp.size(); j++)

{

for (int k = 0; k < pre.size(); k++)

{

if (j == k)

{

continue;

}

dp[j] = min(dp[j], pre[k] + grid[i][j]);

}

}

pre.swap(dp);

}

return *std::min_element(pre.begin(),pre.end());

}

void GetTop2(vector<std::pair>& pre, const vector& v)

{

for (int i = 0; i < v.size(); i++)

{

const int& iValue = v[i];

if (pre.size() < 2)

{

pre.emplace_back(i, iValue);

}

else

{

if (iValue < pre[1].second)

{

pre.erase(pre.begin());

pre.emplace_back(i, iValue);

}

else if (iValue < pre[0].second)

{

pre[0].first = i;

pre[0].second = iValue;

}

}

}

}

};

2023年2月

class Solution {

public:

int minFallingPathSum(vector& grid) {

if (1 == grid.size())

{

return grid[0][0];

}

vector<std::pair> pre;

GetTopN(pre, grid[0],2);

for (int i = 1; i < grid.size(); i++)

{

vector<std::pair> cur;

GetTopN(cur, grid[i],3);

vector<std::pair> dp;

for (auto& it : cur)

{

if (it.first == pre[1].first)

{

dp.emplace_back(it.first, it.second + pre[0].second);

}

else

{

dp.emplace_back(it.first, it.second + pre[1].second);

}

}

if (dp.size() > 2)

{

int iMaxIndex = 0;

for (int j = 1; j < dp.size(); j++)

{

if (dp[j].second > dp[iMaxIndex].second)

{

iMaxIndex = j;

}

}

dp.erase(dp.begin() + iMaxIndex);

}

//确保dp[0].second大于dp[1].second

if (dp[0].second < dp[1].second)

{

auto tmp = dp[0];

dp.erase(dp.begin());

dp.push_back(tmp);

}

pre.swap(dp);

}

return min(pre[0].second, pre[1].second);

}

void GetTopN(vector<std::pair>& pre, const vector& v, int n)

{

for (int i = 0; i < v.size(); i++)

{

const int& iValue = v[i];

bool bInsert = false;

for (int j = 0; j < pre.size(); j++)

{

if (iValue > pre[j].second)

{

pre.emplace(pre.begin() + j, i, iValue);

bInsert = true;

break;

}

}

if (!bInsert)

{

pre.emplace_back(i, iValue);

}

if (pre.size() > n)

{

pre.erase(pre.begin());

}

}

}

};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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++**实现。