Đường dẫn tiền xu trong C ++

Giả sử chúng ta có một mảng A (chỉ số bắt đầu từ 1) với N số:A1, A2, ..., AN và một số nguyên khác B. Số nguyên B biểu thị rằng từ bất kỳ chỉ số nào là i trong mảng A, chúng ta có thể nhảy đến bất kỳ một trong những vị trí trong mảng A được lập chỉ mục i + 1, i + 2,…, i + B nếu vị trí này có thể được chuyển đến. Ngoài ra, nếu chúng ta bước vào chỉ số i, chúng ta phải trả cho Ai một lượng xu. Nếu Ai là -1, điều đó có nghĩa là chúng ta không thể chuyển đến vị trí được lập chỉ mục i trong mảng.

Bây giờ, khi chúng ta bắt đầu từ vị trí được lập chỉ mục 1 trong mảng A và mục tiêu của chúng ta là đạt được vị trí được lập chỉ mục N bằng cách sử dụng số tiền tối thiểu. Chúng ta phải trả về đường dẫn của các chỉ mục (bắt đầu từ 1 đến N) trong mảng mà chúng ta nên thực hiện để đi đến vị trí N được lập chỉ mục bằng cách sử dụng số tiền tối thiểu. Nếu chúng ta có nhiều con đường với cùng một chi phí, chúng ta phải tìm con đường nhỏ nhất về mặt từ vựng. Và nếu chúng ta không có con đường khả thi nào như vậy để đến địa điểm N được lập chỉ mục thì chúng ta sẽ trả về một mảng trống.

Vì vậy, nếu đầu vào là [1,2,4, -1,2], 2, thì đầu ra sẽ là [1,3,5]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của A

• Xác định ret mảng

• Xác định chi phí mảng có kích thước n và điền vào giá trị này bằng inf

• Xác định một mảng tiếp theo có kích thước n và điền vào mảng này với -1

• nếu không n là khác 0 hoặc A [n - 1] giống -1, thì -

  • endPoint:=n - 1

• chi phí [n - 1] =A [n - 1]

• để khởi tạo i:=n - 2, khi i> =0, cập nhật (giảm i đi 1), thực hiện -

  • nếu A [i] giống -1, thì -

    • Bỏ qua phần sau, chuyển sang phần tiếp theo

  • đối với j trong phạm vi i + 1 đến tối thiểu là (n - 1) và i + B, tăng j thêm 1 -

    • nếu cost [j] + A [i]

      • cost [i]:=cost [j] + A [i]

      • tiếp theo [i]:=j

      • endPoint:=i

• nếu endPoint không bằng 0, thì -

  • trả về mảng trống

• cho endPoint không bằng -1, hãy cập nhật endPoint =next [endPoint], do -

  • chèn endPoint + 1 vào cuối ret

• trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{1,2,4,-1,2}, 2

Đầu ra

[1, 3, 5, ]