N개의 숫자 A1, A2, ..., AN 및 또 다른 정수 B가 있는 배열 A(색인이 1에서 시작)가 있다고 가정합니다. 정수 B는 배열 A의 임의의 인덱스에서 i가 있음을 나타냅니다. 배열 A의 위치 중 하나는 i+1, i+2, …, i+B 인덱싱됩니다. 또한 인덱스 i를 밟으면 Ai만큼의 코인을 지불해야 합니다. Ai가 -1이면 배열에서 인덱스 i인 위치로 이동할 수 없음을 의미합니다.
이제 배열 A에서 인덱스 1인 장소에서 시작하여 최소 코인을 사용하여 인덱스 N 장소에 도달하는 것이 목표입니다. 최소 코인을 사용하여 인덱스 N 위치에 도달하기 위해 취해야 하는 배열의 인덱스 경로(1에서 N부터 시작)를 반환해야 합니다. 동일한 비용을 가진 여러 경로가 있는 경우 사전순으로 가장 작은 경로를 찾아야 합니다. N으로 인덱싱된 장소에 도달할 수 있는 가능한 경로가 없는 경우 빈 배열을 반환합니다.
따라서 입력이 [1,2,4,-1,2], 2와 같으면 출력은 [1,3,5]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=A의 크기
-
ret 배열 정의
-
크기가 n인 배열 비용을 정의하고 inf
로 채웁니다. -
크기가 n인 배열을 정의하고 -1로 채우십시오.
-
n이 0이 아니거나 A[n - 1]이 -1과 같으면 −
-
끝점 :=n - 1
-
-
비용[n - 1] =A[n - 1]
-
initialize i :=n - 2의 경우 i>=0일 때 업데이트(i를 1만큼 감소), −
-
A[i]가 -1과 같으면 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
범위 i + 1에서 (n - 1) 및 i + B의 최소값까지 j에 대해 j를 1 −
증가-
비용[j] + A[i] <비용[i]이면 -
-
비용[i] :=비용[j] + A[i]
-
다음[i] :=j
-
끝점 :=i
-
-
-
-
endPoint가 0이 아닌 경우 -
-
빈 배열 반환
-
-
endPoint가 -1과 같지 않은 경우 endPoint =next[endPoint]를 업데이트하고 -
를 수행합니다.-
ret의 끝에 endPoint + 1 삽입
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> cheapestJump(vector<int>& A, int B) {
int n = A.size();
vector <int> ret;
vector <int> cost(n, 1e9);
vector <int> next(n, -1);
if(!n || A[n - 1] == -1) return {};
int endPoint = n - 1;
cost[n - 1] = A[n - 1];
for(int i = n - 2; i >= 0; i--){
if(A[i] == -1) continue;
for(int j = i + 1 ; j <= min(n - 1, i + B); j++){
if(cost[j] + A[i] < cost[i]){
cost[i] = cost[j] + A[i];
next[i] = j;
endPoint = i;
}
}
}
if(endPoint != 0) return {};
for(;endPoint != - 1; endPoint = next[endPoint]){
ret.push_back(endPoint + 1);
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {1,2,4,-1,2};
print_vector(ob.cheapestJump(v, 2));
} 입력
{1,2,4,-1,2}, 2 출력
[1, 3, 5, ]