ค่าใช้จ่ายขั้นต่ำสำหรับตั๋วเดินทางใน C++

ปัญหาค่าใช้จ่ายขั้นต่ำสำหรับตั๋วเดินทาง (Minimum Cost For Tickets)

สมมติว่ามีประเทศหนึ่งที่นิยมเดินทางด้วยรถไฟ เราวางแผนเดินทางล่วงหน้าหนึ่งปี มีอาร์เรย์เก็บวันที่เราจะเดินทาง (วันที่เป็นจำนวนเต็ม 1 ถึง 365) ตั๋วรถไฟขาย 3 แบบ:

• ตั๋ว 1 วัน ราคา costs[0] ดอลลาร์
• ตั๋ว 7 วัน ราคา costs[1] ดอลลาร์
• ตั๋ว 30 วัน ราคา costs[2] ดอลลาร์

ตั๋วแต่ละแบบอนุญาตให้เดินทางได้ติดต่อกันตามจำนวนวัน เช่น ตั๋ว 7 วันที่ซื้อในวันที่ 2 จะครอบคลุมวันที่ 2-8 เราต้องหาค่าใช้จ่ายขั้นต่ำเพื่อเดินทางในทุกวันที่กำหนด

ตัวอย่าง: days = [1,4,6,7,8,20], costs = [2,7,15] ผลลัพธ์คือ 11

คำอธิบาย: วันที่ 1 ซื้อตั๋ว 1 วัน ($2) ครอบคลุมวันที่ 1, วันที่ 3 ซื้อตั๋ว 7 วัน ($7) ครอบคลุมวันที่ 3-9, วันที่ 20 ซื้อตั๋ว 1 วัน ($2) ครอบคลุมวันที่ 20 รวม $11

ขั้นตอนการแก้ปัญหา (Dynamic Programming)

1. สร้างอาร์เรย์ dp ขนาด 366 (ดัชนี 1-365)
2. กำหนด j := 0 (ดัชนีของอาร์เรย์ days)
3. วนลูป i จาก 1 ถึง 365:
   • dp[i] := costs[0] + dp[i-1] (ซื้อตั๋ว 1 วัน)
   • ถ้า i-7 ≥ 0 แล้ว dp[i] := min(dp[i], dp[i-7] + costs[1]) (พิจารณาตั๋ว 7 วัน)
   • ถ้า i-30 ≥ 0 แล้ว dp[i] := min(dp[i], dp[i-30] + costs[2]) (พิจารณาตั๋ว 30 วัน)
   • ถ้า j < days.size() และ days[j] == i เพิ่ม j (เป็นวันเดินทาง ไม่ต้องทำอะไรเพิ่ม)
   • มิฉะนั้น dp[i] := min(dp[i], dp[i-1]) (ไม่ใช่วันเดินทาง ค่าใช้จ่ายเท่ากับวันก่อนหน้า)
4. คืนค่า dp[365]

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

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

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        vector<int> dp(366, 0);
        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], dp[i - 7] + costs[1]);
            if (i - 30 >= 0) dp[i] = min(dp[i], dp[i - 30] + costs[2]);
            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);
    return 0;
}

อินพุทและเอาต์พุทตัวอย่าง

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

Output: 11