数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++跳跃游戏V
假设我们有一个名为arr的整数数组和一个整数d。一步之内，我们可以从索引i跳转到：
i + x，其中：i + x < n 且 x 的范围是1到d。
i - x，其中：i - x >= 0 且 x 的范围是1到d。
这里n是数组的大小。此外，只有当arr[i] > arr[j]且arr[i] > arr[k]（对于i和j之间的所有索引k）时，我们才能从索引i跳转到索引j。我们可以选择数组的任何索引并开始跳跃。我们必须找到我们可以访问的最大索引数。
因此，如果输入类似于d = 2，高度类似于：
那么输出将是4，我们可以从索引10开始。我们可以从索引10 -> 8 -> 6 -> 7跳转，如图所示。因此，如果我们从索引6开始，我们只能跳转到索引7。我们不能跳转到索引5，因为13 > 9。我们不能跳转到索引4，因为索引5介于索引4和6之间，并且13 > 9。而且，我们不能从索引3跳转到索引2或索引1。
为了解决这个问题，我们将遵循以下步骤：
定义一个数组dp
定义一个函数solve()，它将接收一个数组arr、idx和d，
如果dp[idx]不等于-1，则：
返回dp[idx]
ret := 1
n := arr的大小
对于初始化i := idx + 1，当i < n时，更新（i增加1），执行：
如果i > idx + d，则：
退出循环
如果arr[i] >= arr[idx]，则：
退出循环
ret := ret和1 + solve(arr, i, d)中的最大值
对于初始化i := idx - 1，当i >= 0时，更新（i减少1），执行：
如果i < idx - d，则：
退出循环
如果arr[i] >= arr[idx]，则：
退出循环
ret := ret和1 + solve(arr, i, d)中的最大值
dp[idx] := ret
返回ret
从主方法执行以下操作：
n := arr的大小
dp := 定义一个大小为n的数组并将其填充为-1
ret := 1
对于初始化i := 0，当i < n时，更新（i增加1），执行：
ret := ret和solve(arr, i, d)中的最大值
返回ret
让我们看看下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> dp;
int solve(vector <int>& arr, int idx, int d){
if (dp[idx] != -1)
return dp[idx];
int ret = 1;
int n = arr.size();
for (int i = idx + 1; i < n; i++) {
if (i > idx + d)
break;
if (arr[i] >= arr[idx])
break;
ret = max(ret, 1 + solve(arr, i, d));
}
for (int i = idx - 1; i >= 0; i--) {
if (i < idx - d)
break;
if (arr[i] >= arr[idx])
break;
ret = max(ret, 1 + solve(arr, i, d));
}
return dp[idx] = ret;
}
int maxJumps(vector<int>& arr, int d) {
int n = arr.size();
dp = vector<int>(n, -1);
int ret = 1;
for (int i = 0; i < n; i++) {
ret = max(ret, solve(arr, i, d));
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {6,4,14,6,8,13,9,7,10,6,12};
cout << (ob.maxJumps(v, 2));
}输入
{6,4,14,6,8,13,9,7,10,6,12}, 2输出
4
564 次浏览
