Chi phí tối thiểu cho vé tàu trong C++

Giả sử có một quốc gia nổi tiếng với du lịch đường sắt, chúng ta đã lên kế hoạch đi tàu hỏa một năm trước. Chúng ta có một mảng chứa các ngày trong năm mà chúng ta sẽ đi. Mỗi ngày là một số nguyên từ 1 đến 365. Vé tàu được bán theo ba cách:

• Vé 1 ngày giá costs[0] đô la;
• Vé 7 ngày giá costs[1] đô la;
• Vé 30 ngày giá costs[2] đô la.

Các vé cho phép đi lại liên tiếp trong số ngày tương ứng. Ví dụ, nếu mua vé 7 ngày vào ngày 2, ta có thể đi từ ngày 2 đến ngày 8. Ta cần tìm số tiền tối thiểu để đi tất cả các ngày trong danh sách cho trước. Nếu đầu vào là days = [1,4,6,7,8,20] và costs = [2,7,15], đầu ra sẽ là 11.

Giải thích: Ngày 1 mua vé 1 ngày ($2), ngày 3 mua vé 7 ngày ($7) bao phủ ngày 3-9, ngày 20 mua vé 1 ngày ($2). Tổng cộng $11.

Giải thuật

• Tạo mảng dp kích thước 366.
• j := 0.
• Với i từ 1 đến 365:
  • dp[i] := costs[0] + dp[i-1]
  • Nếu i-7 ≥ 0, dp[i] := min(dp[i-7] + costs[1], dp[i])
  • Nếu i-30 ≥ 0, dp[i] := min(dp[i-30] + costs[2], dp[i])
  • Nếu j < days.size() và days[j] == i, tăng j; ngược lại dp[i] := min(dp[i], dp[i-1])
• Trả về dp[365].

Ví dụ mã C++

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

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        vector<int> dp(366);
        int j = 0;
        for (int i = 1; i < 366; i++) {
            dp[i] = costs[0] + dp[i - 1];
            if (i - 7 >= 0) dp[i] = min(dp[i - 7] + costs[1], dp[i]);
            if (i - 30 >= 0) dp[i] = min(dp[i - 30] + costs[2], dp[i]);
            if (j < days.size() && days[j] == i) j++;
            else dp[i] = min(dp[i], dp[i - 1]);
        }
        return dp[365];
    }
};

int main() {
    vector<int> v = {1,4,6,7,8,20};
    vector<int> v1 = {2,7,15};
    Solution ob;
    cout << ob.mincostTickets(v, v1);
}

Đầu vào

[1,4,6,7,8,20] [2,7,15]

Đầu ra

11