สมมติว่ามีประเทศหนึ่งที่เป็นที่นิยมสำหรับการเดินทางด้วยรถไฟ เราได้วางแผนการเดินทางด้วยรถไฟล่วงหน้าหนึ่งปี เรามีอาร์เรย์ที่ถือวันของปีที่เราจะเดินทาง ในแต่ละวันเป็นจำนวนเต็มตั้งแต่ 1 ถึง 365 ตั๋วรถไฟมีจำหน่ายสามวิธี -
-
บัตรผ่านประเภท 1 วันจำหน่ายในราคา[0] ดอลลาร์
-
บัตรผ่านประเภท 1 วันจำหน่ายในราคา[0] ดอลลาร์
-
บัตรผ่าน 30 วันขายในราคา[2] ดอลลาร์
ที่นี่บัตรผ่านอนุญาตให้เดินทางติดต่อกันหลายวัน ตัวอย่างเช่น หากเราได้รับบัตรผ่าน 7 วันในวันที่ 2 เราก็สามารถเดินทางได้ 7 วัน:วันติดต่อกัน (2, 3, 4, 5, 6, 7 และ 8) เราต้องหาจำนวนเงินขั้นต่ำที่เราต้องเดินทางทุกวันในรายชื่อวันที่กำหนด ดังนั้นหากอินพุตเป็น [1,4,6,7,8,20] และต้นทุนเป็น [2,7,15] ผลลัพธ์จะเป็น 11
ในวันที่ 1 เราซื้อบัตร 1 วันในราคา[0] =$2 ซึ่งครอบคลุมวันที่ 1 วันที่ 3 เราซื้อบัตรแบบ 7 วัน ดังนั้น ราคา[1] =$7 ซึ่งครอบคลุมวันที่ 3 ถึง 9 และในวันที่ 20 ซื้อบัตรอีกครั้งเป็นเวลา 1 วัน ดังนั้นราคา[0] =$2 ซึ่งครอบคลุมวันที่ 20 ดังนั้นยอดใช้จ่ายทั้งหมด $11
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สร้างหนึ่งอาร์เรย์ที่เรียกว่า dp ขนาด 366
-
เจ :=0
-
สำหรับผมอยู่ในช่วง 1 ถึง 366
-
dp[i] :=cost[0] + dp[i - 1]
-
ถ้า i – 7>=0 แล้ว dp[i] :=ขั้นต่ำของ dp[i - 7] + cost[1] และ dp[i]
-
ถ้า i – 30>=0 แล้ว dp[i] :=ขั้นต่ำของ dp[i - 30] + cost[2] และ dp[i]
-
ถ้า j <ขนาดของอาร์เรย์วันและวัน[j] =i ให้เพิ่ม j ขึ้น 1 มิฉะนั้น dp[i] :=ขั้นต่ำของ dp[i], dp[i – 1]
-
-
กลับ dp[365]
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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];
}
};
main(){
vector<int> v = {1,4,6,7,8,20};
vector<int> v1 = {2,7,15};
Solution ob;
cout << (ob.mincostTickets(v, v1));
} อินพุต
[1,4,6,7,8,20] [2,7,15]
ผลลัพธ์
11
