資料結構
網路
關係資料庫管理系統 (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 次瀏覽
