เส้นทางเหรียญใน C++

ปัญหา

สมมติว่าเรามีอาร์เรย์ A (ดัชนีเริ่มที่ 1) มี N ตัวเลข: A1, A2, ..., AN และอีกจำนวนเต็มหนึ่งคือ B จำนวนเต็ม B หมายความว่าจากดัชนี i ใดๆ ในอาร์เรย์ A เราสามารถกระโดดไปยังตำแหน่งใดๆ ในอาร์เรย์ A ที่มีดัชนี i+1, i+2, ..., i+B ได้ หากตำแหน่งนั้นสามารถกระโดดไปได้ นอกจากนี้ หากเรายืนบนดัชนี i เราต้องจ่ายเหรียญจำนวน Ai หาก Ai เป็น -1 หมายความว่าเราไม่สามารถกระโดดไปยังตำแหน่งที่มีดัชนี i ในอาร์เรย์ได้

ตอนนี้ เมื่อเราเริ่มจากตำแหน่งที่มีดัชนี 1 ในอาร์เรย์ A และเป้าหมายคือไปถึงตำแหน่งที่มีดัชนี N โดยใช้เหรียญน้อยที่สุด เราต้องคืนค่าเส้นทางของดัชนี (เริ่มจาก 1 ถึง N) ในอาร์เรย์ที่เราควรเดินเพื่อไปถึงตำแหน่งที่มีดัชนี N โดยใช้เหรียญน้อยที่สุด หากมีหลายเส้นทางที่มีค่าใช้จ่ายเท่ากัน เราต้องหาเส้นทางที่เล็กที่สุดในแบบเล็กซิโคกราฟิก และหากไม่มีเส้นทางที่เป็นไปได้เพื่อไปถึงตำแหน่งที่มีดัชนี N เราจะคืนค่าอาร์เรย์ว่าง

เช่น ถ้าผนวกเข้าเป็น [1,2,4,-1,2], 2 ผลลัพธ์จะเป็น [1,3,5]

วิธีแก้ปัญหา

1. n := ขนาดของ A
2. กำหนดอาร์เรย์ ret
3. กำหนดอาร์เรย์ cost ขนาด n และเติมด้วย inf
4. กำหนดอาร์เรย์ next ขนาด n และเติมด้วย -1
5. ถ้า n เป็น 0 หรือ A[n-1] เท่ากับ -1 แล้ว endPoint := n-1
6. cost[n-1] = A[n-1]
7. for i := n-2 ถึง 0 (ลดทีละ 1) ทำ:
   • ถ้า A[i] เท่ากับ -1 ข้ามรอบนี้
   • for j ในช่วง i+1 ถึง min(n-1, i+B) ทำ:
     • ถ้า cost[j] + A[i] < cost[i] แล้ว:
       • cost[i] := cost[j] + A[i]
       • next[i] := j
       • endPoint := i
8. ถ้า endPoint ไม่เท่ากับ 0 คืนค่าอาร์เรย์ว่าง
9. for endPoint ไม่เท่ากับ -1 อัปเดต endPoint = next[endPoint] ทำ:
   • เพิ่ม endPoint + 1 เข้าไปท้าย ret
10. คืนค่า ret

ตัวอย่างโค้ด C++

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

int 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, ]