【动态规划】【C++算法】741摘樱桃

2024-01-20 10:52
文章标签 算法 动态 规划 c++ 741 樱桃

本文主要是介绍【动态规划】【C++算法】741摘樱桃，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

【动态规划】【数学】【C++算法】18赛车

涉及知识点

动态规划

LeetCode741 摘樱桃

给你一个 n x n 的网格 grid ，代表一块樱桃地，每个格子由以下三种数字的一种来表示：
0 表示这个格子是空的，所以你可以穿过它。
1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
-1 表示这个格子里有荆棘，挡着你的路。
请你统计并返回：在遵守下列规则的情况下，能摘到的最多樱桃数：
从位置 (0, 0) 出发，最后到达 (n - 1, n - 1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为 0 或者 1 的格子）；
当到达 (n - 1, n - 1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为 0 ）；
如果在 (0, 0) 和 (n - 1, n - 1) 之间不存在一条可经过的路径，则无法摘到任何一个樱桃。
示例 1：
输入：grid = [[0,1,-1],[1,0,-1],[1,1,1]]
输出：5
解释：玩家从 (0, 0) 出发：向下、向下、向右、向右移动至 (2, 2) 。
在这一次行程中捡到 4 个樱桃，矩阵变成 [[0,1,-1],[0,0,-1],[0,0,0]] 。
然后，玩家向左、向上、向上、向左返回起点，再捡到 1 个樱桃。
总共捡到 5 个樱桃，这是最大可能值。
示例 2：
输入：grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
输出：0
参数范围：
n == grid.length
n == grid[i].length
1 <= n <= 50
grid[i][j] 为 -1、0 或 1
grid[0][0] != -1
grid[n - 1][n - 1] != -1

动态规划

起程和返程可能进过同一地点，此处的樱桃只能摘一次。转换一下思路：假定有两个机器人，第一个机器按起程路线走，第二个机器人按返程路线反向走。由于只能向右下，所以不会存在环，也不会往回走。假定移动step次后，第一个机器人在r1行，第二个机器人在r2行，则第一个机器人在第step-c1列，第二个机器人在step-c2列。同一格行列号相同 ==> 行列号之和(step)相同 ==> 不同step，一定不是同一格子。
小技巧： setp相同时，只需要判断行号或列号是否相同。

动态规划的填表顺序

时间复杂度:O((n*2)nn) 三层循环，第一层从小到大枚举step；第二层枚举第一个机器人所在行，第二层枚举第二个机器人所在行。

动态规划的状态表示

pre[r1][r2]表示 step步后，机器人一在r1，机器人二在r2 已经收获的最大樱桃数。
dp[nr1][nr2]表示 step+1步后，机器人一在nr1，机器人二在nr2 已经收获的最大樱桃数。

动态规划的转移方程

int i2 = (nr1 == nr2) ? 0 : grid[nr2][nc2];//如果两个机器人 在同一位置不重复计算dp[nr1][nr2] = max(dp[nr1][nr2],pre[r1][r2] + grid[nr1][nc1] + i2 );

动态规划的初始状态

pre[0][0] = grid[0][0];

动态规划的返回值

return (-1==pre.back().back())?0: pre.back().back();

代码

封装类

class CEnumGridEdge
{
public:void Init(){for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){Move(r, c, r + 1, c);Move(r, c, r - 1, c);Move(r, c, r, c + 1);Move(r, c, r, c - 1);}}}const int m_r, m_c;
protected:CEnumGridEdge(int r, int c) :m_r(r), m_c(c){}void Move(int preR, int preC, int r, int c){if ((r < 0) || (r >= m_r)){return;}if ((c < 0) || (c >= m_c)){return;}OnEnumEdge(preR, preC, r, c);};virtual void OnEnumEdge(int preR, int preC, int r, int c) = 0;
};

复制类

class TNeiBoForGrid :  public CEnumGridEdge
{
public:	TNeiBoForGrid(const vector<vector<int>>& grid):m_grid(grid),CEnumGridEdge(grid.size(),grid.front().size()){m_vNext.assign(m_r, vector < vector<pair<int, int>>>(m_c));Init();}virtual void OnEnumEdge(int preR, int preC, int r, int c){if ((-1 == m_grid[preR][preC]) || (-1 == m_grid[r][c])){return;}if ((preR > r) || (preC > c)){return;}m_vNext[preR][preC].emplace_back(r, c);}const vector<vector<int>>& m_grid;vector < vector < vector<pair<int, int>>>> m_vNext;
};

核心代码

class Solution {
public:int cherryPickup(vector<vector<int>>& grid) {TNeiBoForGrid neiBo(grid);vector<vector<int>> pre(neiBo.m_r, vector<int>(neiBo.m_r, -1));pre[0][0] = grid[0][0];for (int step = 0; step < neiBo.m_r + neiBo.m_c - 2; step++){vector<vector<int>> dp(neiBo.m_r, vector<int>(neiBo.m_r, -1));for(int r1 = max(0,step-(neiBo.m_c-1)) ; r1 <= min(step, neiBo.m_r-1);r1++ )for (int r2 = max(0, step - (neiBo.m_c - 1)); r2 <= min(step, neiBo.m_r-1); r2++){if (-1 == pre[r1][r2]){continue;}const int c1 = step - r1;const int c2 = step - r2;for (const auto& [nr1, nc1] : neiBo.m_vNext[r1][c1]){for (const auto& [nr2, nc2] : neiBo.m_vNext[r2][c2]){int i2 = (nr1 == nr2) ? 0 : grid[nr2][nc2];//如果两个机器人 在同一位置不重复计算dp[nr1][nr2] = max(dp[nr1][nr2],pre[r1][r2] + grid[nr1][nc1] + i2 );}}}pre.swap(dp);}return (-1==pre.back().back())?0: pre.back().back();}
};

测试用例

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} };auto res = sln.cherryPickup(grid);Assert(0, res);}{Solution sln;grid = { {0} };auto res = sln.cherryPickup(grid);Assert(0, res);}{Solution sln;grid = { {1} };auto res = sln.cherryPickup(grid);Assert(1, res);}{Solution sln;grid = { {0,1,-1},{1,0,-1},{1,1,1} };auto res = sln.cherryPickup(grid);Assert(5, res);}{Solution sln;grid = { {1,1,-1},{1,-1,1},{-1,1,1} };auto res = sln.cherryPickup(grid);Assert(0, res);}{Solution sln;grid = { {1, -1, 1, -1, 1, 1, 1, 1, 1, -1}, { -1,1,1,-1,-1,1,1,1,1,1 }, { 1,1,1,-1,1,1,1,1,1,1 }, { 1,1,1,1,1,1,1,1,1,1 }, { -1,1,1,1,1,1,1,1,1,1 }, { 1,-1,1,1,1,1,-1,1,1,1 }, { 1,1,1,-1,1,1,-1,1,1,1 }, { 1,-1,1,-1,-1,1,1,1,1,1 }, { 1,1,-1,-1,1,1,1,-1,1,-1 }, { 1,1,-1,1,1,1,1,1,1,1 } };auto res = sln.cherryPickup(grid);Assert(0, res);}}

2023年1月

class Solution {
public:
int cherryPickup(vector<vector>& grid) {
m_c = grid.size();
m_preDp.assign(1, vector(1, grid[0][0]));
for (int len = 1; len <= m_c * 2 - 2; len++)
{
vector<vector> dp;
dp.assign(len + 1, vector(len + 1, -1));
for (int r1 = 0; r1 <= min(len,m_c-1); r1++)
{
for (int r2 = 0; r2 <= r1; r2++)
{
const int c1 = len - r1;
const int c2 = len - r2;
if ((c1 >= m_c) || (c2 >= m_c))
{
continue;
}
if ((grid[r1][c1] < 0) || (grid[r2][c2] < 0))
{
continue;
}
int tmp1 = grid[r1][c1];
if (r1 != r2)
{
tmp1 += grid[r2][c2];
}
int tmp2 = -1;
Test(tmp2, grid, r1, r2, len - 1);
Test(tmp2, grid, r1 - 1, r2, len - 1);
Test(tmp2, grid, r1, r2 - 1, len - 1);
Test(tmp2, grid, r1 - 1, r2 - 1, len - 1);
if (tmp2 < 0)
{
continue;
}
dp[r1][r2] = tmp1 + tmp2;
}
}
m_preDp.swap(dp);
}
return max(0,m_preDp[m_c-1][m_c-1]);
}
void Test(int& iNew,const vector<vector>& grid,int r1, int r2, int iPreLen)
{
if (r1 < 0 || r1 > iPreLen)
{
return;
}
if (r2 < 0 || r2 > iPreLen)
{
return;
}
if (r1 < r2)
{
int tmp = r1;
r1 = r2;
r2 = tmp;
}
if (m_preDp[r1][r2] < 0)
{
return;
}
iNew = max(iNew,m_preDp[r1][r2]);
}
int m_c;
vector<vector> m_preDp;
};

扩展阅读

视频课程

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

这篇关于【动态规划】【C++算法】741摘樱桃的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/625779。

相关文章

Windows下C++使用SQLitede的操作过程

Windows下C++使用SQLitede的操作过程

《Windows下C++使用SQLitede的操作过程》本文介绍了Windows下C++使用SQLite的安装配置、CppSQLite库封装优势、核心功能（如数据库连接、事务管理）、跨平台支持及性能优... 目录Windows下C++使用SQLite1、安装2、代码示例CppSQLite：C++轻松操作SQ
阅读更多...
C++中RAII资源获取即初始化

C++中RAII资源获取即初始化

《C++中RAII资源获取即初始化》RAII通过构造/析构自动管理资源生命周期,确保安全释放,本文就来介绍一下C++中的RAII技术及其应用,具有一定的参考价值,感兴趣的可以了解一下... 目录一、核心原理与机制二、标准库中的RAII实现三、自定义RAII类设计原则四、常见应用场景1. 内存管理2. 文件操
阅读更多...
C++中零拷贝的多种实现方式

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri
阅读更多...
C++高效内存池实现减少动态分配开销的解决方案

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现：TCMalloc与Jemalloc1. TCM
阅读更多...
C++ 函数 strftime 和时间格式示例详解

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五
阅读更多...
C++作用域和标识符查找规则详解

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域（Scope）和标识符查找（IdentifierLookup）是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找（Ordinary Lookup）2. 限定查找（Qualif
阅读更多...
Java调用C#动态库的三种方法详解

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢？今天,我们... 目录方法1：C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1：创建C#类库（.NET
阅读更多...
MyBatis编写嵌套子查询的动态SQL实践详解

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可
阅读更多...
C/C++ chrono简单使用场景示例详解

C/C++ chrono简单使用场景示例详解

《C/C++chrono简单使用场景示例详解》：本文主要介绍C/C++chrono简单使用场景示例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友... 目录chrono使用场景举例1 输出格式化字符串chrono使用场景China编程举例1 输出格式化字符串示
阅读更多...
C++/类与对象/默认成员函数@构造函数的用法

C++/类与对象/默认成员函数@构造函数的用法

《C++/类与对象/默认成员函数@构造函数的用法》：本文主要介绍C++/类与对象/默认成员函数@构造函数的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录名词概念默认成员函数构造函数概念函数特征显示构造函数隐式构造函数总结名词概念默认构造函数：不用传参就可以
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2