【动态规划】【C++算法】1340. 跳跃游戏 V

简介: 【动态规划】【C++算法】1340. 跳跃游戏 V

作者推荐

【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数

本文涉及知识点

动态规划汇总

LeetCode1340跳跃游戏 V

给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到:

i + x ,其中 i + x < arr.length 且 0 < x <= d 。

i - x ,其中 i - x >= 0 且 0 < x <= d 。

除此以外,你从下标 i 跳到下标 j 需要满足:arr[i] > arr[j] 且 arr[i] > arr[k] ,其中下标 k 是所有 i 到 j 之间的数字(更正式的,min(i, j) < k < max(i, j))。

你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。

请注意,任何时刻你都不能跳到数组的外面。

示例 1:

输入:arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2

输出:4

解释:你可以从下标 10 出发,然后如上图依次经过 10 --> 8 --> 6 --> 7 。

注意,如果你从下标 6 开始,你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。你也不能跳到下标 4 处,因为下标 5 在下标 4 和 6 之间且 13 > 9 。

类似的,你不能从下标 3 处跳到下标 2 或者下标 1 处。

示例 2:

输入:arr = [3,3,3,3,3], d = 3

输出:1

解释:你可以从任意下标处开始且你永远无法跳到任何其他坐标。

示例 3:

输入:arr = [7,6,5,4,3,2,1], d = 1

输出:7

解释:从下标 0 处开始,你可以按照数值从大到小,访问所有的下标。

示例 4:

输入:arr = [7,1,7,1,7,1], d = 2

输出:2

示例 5:

输入:arr = [66], d = 1

输出:1

提示:

1 <= arr.length <= 1000

1 <= arr[i] <= 105

1 <= d <= arr.length

动态规划

动态规划的状态表示

dp[i] 表示以arr[i]为起点的最多跳跃次数。

动态规划的转移方程

以左跳为例

dp[i]=max(dp[j]+1),j的范围{ 初始值: i − 1 合法值,非法则停止: ( j > = 0 ) 且 ( i − j ) < = d 且 a r r [ i ] > a r r [ j ] 增量 : j − − \begin{cases}初始值:& i-1\\ 合法值,非法则停止:& (j>=0)且(i-j)<=d 且arr[i] > arr[j] \\ 增量: &j-- \\ \end{cases}初始值:合法值,非法则停止:增量:i1(j>=0)(ij)<=darr[i]>arr[j]j

动态规划的初始值

全为1。

动态规划的填表顺序

arr[i]从小大到

动态规划的返回值

dp的最大值

鸡肋的优化

无论是左跳还是右跳,都只会跳到能跳的最高。但最高可能有多个。比如:

33 1 2 3 左跳到第一个3就无法再跳了。

代码

核心代码

class Solution {
public:
  int maxJumps(vector<int>& arr, int d) {
    multimap<int, int> mValueIndex;
    for (int i = 0; i < arr.size(); i++)
    {
      mValueIndex.emplace(arr[i], i);
    }
    vector<int> dp(arr.size(), 1);
    for (const auto& [tmp, i] : mValueIndex)
    {
      for (int j = i - 1; (j >= 0) && (i - j <= d) && (arr[i] > arr[j]); j--)
      {
        dp[i] = max(dp[i], 1 + dp[j]);
      }
      for (int j = i + 1; (j < arr.size()) && (j-i <= d) && (arr[i] > arr[j]); j++)
      {
        dp[i] = max(dp[i], 1 + dp[j]);
      }
    }
    return *std::max_element(dp.begin(), dp.end());
  }
};

测试用例

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<int> arr;
  int d;
  {
    Solution sln;
    arr = { 66 }, d = 1;
    auto res = sln.maxJumps(arr, d);
    Assert(1, res);
  }
  {
    Solution sln;
    arr = { 6, 4, 14, 6, 8, 13, 9, 7, 10, 6, 12 }, d = 2;
    auto res = sln.maxJumps(arr, d);
    Assert(4, res);
  }
  {
    Solution sln;
    arr = { 3,3,3,3 }, d = 2;
    auto res = sln.maxJumps(arr, d);
    Assert(1, res);
  }
  {
    Solution sln;
    arr = { 7, 6, 5, 4, 3, 2, 1 }, d = 1;
    auto res = sln.maxJumps(arr, d);
    Assert(7, res);
  }
  {
    Solution sln;
    arr = { 7, 1, 7, 1, 7, 1 }, d = 2;
    auto res = sln.maxJumps(arr, d);
    Assert(2, res);
  }
  
}

2023年2月

class Solution {

public:

int maxJumps(vector& arr, int d) {

m_iNums.assign(arr.size(), -1);

m_vJumpPos.resize(arr.size());

LeftJumpPos(m_vJumpPos, arr, d);

RightJumpPos(m_vJumpPos,arr, d);

for (int i = 0; i < arr.size(); i++)

{

Rec(i);

}

//CConsole::Out(m_vJumpPos, “|”);

//CConsole::Out(m_iNums, “|”);

return *std::max_element(m_iNums.begin(),m_iNums.end());

}

int Rec(int iPos)

{

if (-1 != m_iNums[iPos])

{

return m_iNums[iPos];

}

int iMaxNextNum = 0;

for (const auto& i : m_vJumpPos[iPos])

{

iMaxNextNum = max(iMaxNextNum, Rec(i));

}

return m_iNums[iPos] = iMaxNextNum + 1;

}

vector m_iNums;

void LeftJumpPos(vector<vector>& vLeftJumpPos,const vector& arr, int d)

{

vector vLeftIndexs, vLeftValue;

int iHasDo = 0;

for (int i = 0; i < arr.size(); i++)

{

while ((iHasDo < vLeftIndexs.size()) && (vLeftIndexs[iHasDo] + d < i))

{

iHasDo++;

}

auto it = std::upper_bound(vLeftValue.begin() + iHasDo, vLeftValue.end(), arr[i], std::greater());

if (vLeftValue.end() == it)

{

}

else

{

for (auto ij = it; (ij != vLeftValue.end()) && (*it == *ij); ++ij)

{

int index = ij - vLeftValue.begin();

vLeftJumpPos[i].push_back(vLeftIndexs[index]);

}

}

while ((vLeftValue.size() > iHasDo) && (arr[i] > vLeftValue.back()))

{

vLeftIndexs.pop_back();

vLeftValue.pop_back();

}

vLeftIndexs.push_back(i);

vLeftValue.push_back(arr[i]);

}

}

void RightJumpPos(vector<vector>& vJumpPos, const vector& arr, int d)

{

vector vIndexs, vValue;

int iHasDo = 0;

for (int i = arr.size() - 1; i >= 0; i–)

{

while ((iHasDo < vIndexs.size()) && (vIndexs[iHasDo] - d > i))

{

iHasDo++;

}

auto it = std::upper_bound(vValue.begin() + iHasDo, vValue.end(), arr[i], std::greater());

if (vValue.end() == it)

{

}

else

{

for (auto ij = it; (ij != vValue.end()) && (*it == *ij);++ij)

{

int index = ij - vValue.begin();

vJumpPos[i].push_back(vIndexs[index]);

}

}

while ((vValue.size() > iHasDo) && (arr[i] > vValue.back()))

{

vIndexs.pop_back();

vValue.pop_back();

}

vIndexs.push_back(i);

vValue.push_back(arr[i]);

}

}

vector<vector> m_vJumpPos;

};

2023年7月版

class Solution {

public:

int maxJumps(vector& arr, int d) {

m_c = arr.size();

m_d = d;

vector<vector> vLeft,vRight,vMove(m_c);

GetLeft(vLeft, arr);

GetRight(vRight, arr);

for (int i = 0; i < m_c; i++)

{

vMove[i].insert(vMove[i].end(), vLeft[i].begin(), vLeft[i].end());

const int right = m_c - 1 - i;

vMove[i].insert(vMove[i].end(), vRight[right].begin(), vRight[right].end());

}

//值从小到大出来

std::multimap<int, int> mValueIndexs;

for (int i = 0; i < arr.size(); i++)

{

mValueIndexs.emplace(arr[i], i);

}

vector vRet(m_c, -1);

for (const auto& it : mValueIndexs)

{

int iCanMove = 0;

for (const auto& next : vMove[it.second])

{

iCanMove = max(iCanMove, vRet[next]);

}

vRet[it.second] = iCanMove+1;

}

return *std::max_element(vRet.begin(), vRet.end());

}

void GetLeft(vector<vector>& vMove, const vector& arr)

{

std::stack sta;

for (int i = 0; i < arr.size(); i++)

{

int iMoveValue = -1;

vMove.emplace_back();

while (sta.size() && (arr[sta.top()] < arr[i]))

{

const int iTop = sta.top();

sta.pop();

if (abs(iTop - i) <= m_d)

{

if (arr[iTop] != iMoveValue)

{

vMove.back().clear();

}

vMove.back().emplace_back(iTop);

iMoveValue = arr[iTop];

}

}

sta.emplace(i);

}

}

void GetRight(vector<vector>& vMove, const vector& arr)

{

std::stack sta;

for (int i = m_c - 1; i >= 0; i–)

{

int iMoveValue = -1;

vMove.emplace_back();

while (sta.size() && (arr[sta.top()] < arr[i]))

{

const int iTop = sta.top();

sta.pop();

if (abs(iTop - i) <= m_d)

{

if (arr[iTop] != iMoveValue)

{

vMove.back().clear();

}

vMove.back().emplace_back(iTop);

iMoveValue = arr[iTop];

}

}

sta.emplace(i);

}

}

int m_c;

int m_d;

};

2023年8月版

class Solution {

public:

int maxJumps(vector& arr, int d) {

m_c = arr.size();

m_arr = arr;

m_iD = d;

m_vCanMove.resize(m_c);

DoLeft();

DoRight();

std::multimap<int, int> mHeightIndex;

for ( int i = 0; i < m_c; i++)

{

mHeightIndex.emplace(arr[i], i);

}

vector vRet(m_c);

for (const auto& it : mHeightIndex)

{

int iPre = 0;

for (const int pr : m_vCanMove[it.second])

{

iPre = max(iPre, vRet[pr]);

}

vRet[it.second] = iPre + 1;

}

return *std::max_element(vRet.begin(), vRet.end());

}

void DoLeft()

{

stack sta;

for (int i = 0; i < m_c; i++)

{

vector vCanMove;

while (sta.size() && (m_arr[sta.top()] < m_arr[i]))

{

if (abs(sta.top() - i) <= m_iD)

{

vCanMove.emplace_back(sta.top());

}

sta.pop();

}

if (vCanMove.size())

{

const int iMax = m_arr[vCanMove.back()];

for (int j = vCanMove.size() - 1; (j >= 0)&&(iMax == m_arr[vCanMove[j]]); j–)

{

m_vCanMove[i].emplace_back(vCanMove[j]);

}

}

sta.emplace(i);

}

}

void DoRight()

{

stack sta;

for (int i = m_c-1 ; i >= 0 ; i–)

{

vector vCanMove;

while (sta.size() && (m_arr[sta.top()] < m_arr[i]))

{

if (abs(sta.top() - i) <= m_iD)

{

vCanMove.emplace_back(sta.top());

}

sta.pop();

}

if (vCanMove.size())

{//只需要考虑移动到次高,如果有多个次高可以一定,全部要考虑

const int iMax = m_arr[vCanMove.back()];

for (int j = vCanMove.size() - 1; (j >= 0) && (iMax == m_arr[vCanMove[j]]); j–)

{

m_vCanMove[i].emplace_back(vCanMove[j]);

}

}

sta.emplace(i);

}

}

vector<vector> m_vCanMove;

vector m_arr;

int m_iD;

int m_c;

};


相关文章
|
1月前
|
负载均衡 算法 安全
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
52 19
|
29天前
|
算法 Java C++
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
48 5
|
1月前
|
设计模式 IDE 编译器
【C++面向对象——类的多态性与虚函数】编写教学游戏:认识动物(头歌实践教学平台习题)【合集】
本项目旨在通过C++编程实现一个教学游戏,帮助小朋友认识动物。程序设计了一个动物园场景,包含Dog、Bird和Frog三种动物。每个动物都有move和shout行为,用于展示其特征。游戏随机挑选10个动物,前5个供学习,后5个用于测试。使用虚函数和多态实现不同动物的行为,确保代码灵活扩展。此外,通过typeid获取对象类型,并利用strstr辅助判断类型。相关头文件如&lt;string&gt;、&lt;cstdlib&gt;等确保程序正常运行。最终,根据小朋友的回答计算得分,提供互动学习体验。 - **任务描述**:编写教学游戏,随机挑选10个动物进行展示与测试。 - **类设计**:基类
33 3
|
1月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
50 2
|
2月前
|
存储 算法 安全
基于红黑树的局域网上网行为控制C++ 算法解析
在当今网络环境中,局域网上网行为控制对企业和学校至关重要。本文探讨了一种基于红黑树数据结构的高效算法,用于管理用户的上网行为,如IP地址、上网时长、访问网站类别和流量使用情况。通过红黑树的自平衡特性,确保了高效的查找、插入和删除操作。文中提供了C++代码示例,展示了如何实现该算法,并强调其在网络管理中的应用价值。
|
1月前
|
存储 算法 安全
基于哈希表的文件共享平台 C++ 算法实现与分析
在数字化时代,文件共享平台不可或缺。本文探讨哈希表在文件共享中的应用,包括原理、优势及C++实现。哈希表通过键值对快速访问文件元数据(如文件名、大小、位置等),查找时间复杂度为O(1),显著提升查找速度和用户体验。代码示例展示了文件上传和搜索功能,实际应用中需解决哈希冲突、动态扩容和线程安全等问题,以优化性能。
|
2月前
|
算法 安全 C++
用 C++ 算法控制员工上网的软件,关键逻辑是啥?来深度解读下
在企业信息化管理中,控制员工上网的软件成为保障网络秩序与提升办公效率的关键工具。该软件基于C++语言,融合红黑树、令牌桶和滑动窗口等算法,实现网址精准过滤、流量均衡分配及异常连接监测。通过高效的数据结构与算法设计,确保企业网络资源优化配置与安全防护升级,同时尊重员工权益,助力企业数字化发展。
65 4
|
3月前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
81 2
|
3天前
|
编译器 C语言 C++
类和对象的简述(c++篇)
类和对象的简述(c++篇)