Đường đi đồng xu trong C++

Mô tả bài toán

Cho mảng A (chỉ số bắt đầu từ 1) gồm N số: A1, A2, ..., AN và số nguyên B. Từ chỉ số i trong mảng, ta có thể nhảy đến bất kỳ vị trí nào trong phạm vi i+1, i+2, ..., i+B (nếu vị trí đó có thể nhảy đến). Nếu bước vào chỉ số i, phải trả Ai đồng xu. Nếu Ai = -1, không thể nhảy đến vị trí i.

Bắt đầu từ chỉ số 1, mục tiêu là đến chỉ số N với chi phí đồng xu tối thiểu. Trả về đường đi các chỉ số (từ 1 đến N) để đạt chi phí nhỏ nhất. Nếu có nhiều đường đi cùng chi phí, chọn đường đi có thứ tự từ điển nhỏ nhất. Nếu không có đường đi nào, trả về mảng rỗng.

Ví dụ: A = [1,2,4,-1,2], B = 2 → Đầu ra: [1,3,5].

Ý tưởng giải pháp (Quy hoạch động)

• n = kích thước mảng A.
• Mảng cost kích thước n, khởi tạo giá trị lớn (inf) — chi phí tối thiểu từ i đến N.
• Mảng next kích thước n, khởi tạo -1 — chỉ số tiếp theo trên đường đi tối ưu.
• Nếu n == 0 hoặc A[n-1] == -1 → trả về mảng rỗng.
• cost[n-1] = A[n-1], endPoint = n-1.
• Duyệt ngược từ i = n-2 về 0:
  • Nếu A[i] == -1 → bỏ qua.
  • Với mỗi j từ i+1 đến min(n-1, i+B):
    • Nếu cost[j] + A[i] < cost[i]:
      • Cập nhật cost[i] = cost[j] + A[i]
      • next[i] = j
      • endPoint = i
• Nếu endPoint != 0 → không thể đến đích từ 0 → trả về mảng rỗng.
• Khôi phục đường đi từ endPoint theo mảng next.

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> 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));
    return 0;
}

Đầu vào

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

Đầu ra

[1, 3, 5, ]