【动态规划】【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<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学院，听白银讲师（也就是鄙人）的讲解。
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++**实现。