本文涉及知识点
动态规划汇总
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());
}
}
}
};
