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

作者推荐

本文涉及知识点

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<int,int> msumtoindex 的key，各行的最小和,value 列下标。 msumtoindex不包括当前行，mdp包括当前行。
只需要比较msumtoindex 最小元素和次小元素。
状态数：n,行数。

动态规划的转移方程

各列和msumtoindex的最小、次小元素结合，最小值为imin。将imin和列号放到mdp中。
转移方程复杂度：o(n)。总复杂度：o(nn)。

动态规划的初始值

{0,1} {0,1}

动态规划的填表顺序

依次处理各行。

动态规划的返回值

msumtoindex.begin().first

map

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

代码

核心代码

class solution {
public:
	int minfallingpathsum(vector<vector<int>>& grid) {
		const int n = grid.size();
		if (1 == n)
		{
			return grid[0][0];
		}
		multimap<int, int> 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<int, int> 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<class t>
void assert(const t& t1, const t& t2)
{
	assert(t1 == t2);
}

template<class t>
void assert(const vector<t>& v1, const vector<t>& 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<int>> 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<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<int, int>>& 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<vector>& grid) {
if (1 == grid.size())
{
return grid[0][0];
}
vector<std::pair<int, int>> pre;
gettopn(pre, grid[0],2);
for (int i = 1; i < grid.size(); i++)
{
vector<std::pair<int, int>> cur;
gettopn(cur, grid[i],3);
vector<std::pair<int, int>> 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<int, int>>& 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学院，听白银讲师（也就是鄙人）的讲解。

如何你想快

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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： vs2019 c++17
或者操作系统：win10 开发环境： vs2022 c++17
如无特殊说明，本算法用**c++**实现。

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

2024年07月28日 • C/C++ •我要评论