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

2024-01-26 01:04

本文主要是介绍【动态规划】【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 最小元素和次小元素。

动态规划的转移方程

各列和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());
}
}
}
};

扩展阅读

视频课程

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

这篇关于【动态规划】【map】【C++算法】1289. 下降路径最小和 II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/645188

相关文章

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

从入门到精通C++11 <chrono> 库特性

《从入门到精通C++11<chrono>库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段(Durat

C++20管道运算符的实现示例

《C++20管道运算符的实现示例》本文简要介绍C++20管道运算符的使用与实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录标准库的管道运算符使用自己实现类似的管道运算符我们不打算介绍太多,因为它实际属于c++20最为重要的

Visual Studio 2022 编译C++20代码的图文步骤

《VisualStudio2022编译C++20代码的图文步骤》在VisualStudio中启用C++20import功能,需设置语言标准为ISOC++20,开启扫描源查找模块依赖及实验性标... 默认创建Visual Studio桌面控制台项目代码包含C++20的import方法。右键项目的属性:

c++中的set容器介绍及操作大全

《c++中的set容器介绍及操作大全》:本文主要介绍c++中的set容器介绍及操作大全,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录​​一、核心特性​​️ ​​二、基本操作​​​​1. 初始化与赋值​​​​2. 增删查操作​​​​3. 遍历方

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决