作者推荐
本文涉及知识点
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 最小元素和次小元素。
动态规划的转移方程
各列和mSumToIndex的最小、次小元素结合，最小值为iMin。将iMin和列号放到mDp中。
动态规划的初始值
{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());
}
}
}
};
