【动态规划】【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] <= 10⁵

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}⎩⎨⎧初始值：合法值，非法则停止：增量:i−1(j>=0)且(i−j)<=d且arr[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;

};