arr이라는 정수 배열과 정수 d가 있다고 가정합니다. 한 단계에서 인덱스 i에서 -
로 이동할 수 있습니다.-
i + x 여기서:i + x
-
i - x 여기서:i - x>=0 및 x 범위 1에서 d.
여기서 n은 배열의 크기입니다. 또한 i와 j 사이의 모든 인덱스 k에 대해 arr[i]> arr[j] 및 arr[i]> arr[k]인 경우에만 인덱스 i에서 인덱스 j로 점프할 수 있습니다. 배열의 인덱스를 선택하고 점프를 시작할 수 있습니다. 방문할 수 있는 최대 인덱스 수를 찾아야 합니다.
따라서 입력이 d =2이고 높이가 다음과 같다면
그러면 출력은 4가 되고 인덱스 10에서 시작할 수 있습니다. 그림과 같이 인덱스 10 --> 8 --> 6 --> 7에서 점프할 수 있습니다. 따라서 인덱스 6에서 시작하면 인덱스 7로만 점프할 수 있습니다. 13> 9 때문에 인덱스 5로 점프할 수 없습니다. 인덱스 5가 인덱스 4와 6 사이에 있고 13> 9이기 때문에 인덱스 4로 점프할 수 없습니다. 또한 인덱스 3에서 인덱스 2 또는 인덱스 1로 이동할 수 없습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
배열 dp 정의
-
solve() 함수를 정의하면 arr, idx, d,
배열이 사용됩니다. -
dp[idx]가 -1과 같지 않으면 -
-
반환 dp[idx]
-
-
렛 :=1
-
n :=arr의 크기
-
initialize i :=idx + 1의 경우, i
-
i> idx + d이면 -
-
루프에서 나오세요
-
-
arr[i]>=arr[idx]이면 -
-
루프에서 나오세요
-
-
ret :=ret 및 1의 최대값 + solve(arr, i, d)
-
-
initialize i :=idx - 1의 경우, i>=0일 때 업데이트(i를 1만큼 감소), −
-
i
-
루프에서 나오세요
-
-
arr[i]>=arr[idx]이면 -
-
루프에서 나오세요
-
-
ret :=ret 및 1의 최대값 + solve(arr, i, d)
-
-
dp[idx] :=렛
-
리턴 렛
-
주요 방법에서 다음을 수행하십시오 -
-
n :=arr의 크기
-
dp :=크기가 n인 배열을 정의하고 -1로 채우십시오.
-
렛 :=1
-
initialize i :=0의 경우, i
-
ret :=ret 및 solve(arr, i, d)의 최대값
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#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