สมมติเรามีรายการเลขเรียงเรียกว่าวันซึ่งเราต้องขึ้นรถเมล์ในแต่ละวัน เราต้องหาต้นทุนที่ต่ำที่สุดในการเดินทางตลอดทั้งวัน ตั๋วรถโดยสารมี 3 ประเภท บัตร 1 วัน 2 เหรียญ บัตร 7 วัน 7 เหรียญ บัตร 30 วัน 25 เหรียญ
ดังนั้นหากอินพุตเป็นเหมือนวัน =[1, 3, 5, 6, 28] ผลลัพธ์จะเป็น 9 เนื่องจากต้นทุนต่ำสุดสามารถทำได้โดยการซื้อบัตร 7 วันในตอนเริ่มต้นแล้ว 1- ผ่านวันที่ 29.
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:
-
n :=จำนวนวันสูงสุด
-
วัน :=ชุดใหม่จากวัน
-
dp :=[0] *(n + 1)
-
สำหรับผมอยู่ในช่วง 1 ถึง n + 1 ทำ
-
ถ้าฉันในวันที่ไม่เป็นศูนย์แล้ว
-
ถ้าฉัน>=30 แล้ว
-
dp[i] :=ขั้นต่ำของ dp[i - 1] + 2, dp[i - 7] + 7, dp[i - 30] + 25
-
-
มิฉะนั้น เมื่อ i>=7 แล้ว
-
dp[i] :=ขั้นต่ำของ dp[i - 1] + 2, dp[i - 7] + 7, 25
-
-
มิฉะนั้น
-
dp[i] :=ขั้นต่ำของ dp[i - 1] + 2, 7
-
-
-
มิฉะนั้น
-
dp[i] :=dp[i - 1]
-
-
-
กลับ dp[n]
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:
ตัวอย่าง
class Solution: def solve(self, days): n = max(days) days = set(days) dp = [0] * (n + 1) for i in range(1, n + 1): if i in days: if i >= 30: dp[i] = min(dp[i - 1] + 2, dp[i - 7] + 7, dp[i - 30] + 25) elif i >= 7: dp[i] = min(dp[i - 1] + 2, dp[i - 7] + 7, 25) else: dp[i] = min(dp[i - 1] + 2, 7) else: dp[i] = dp[i - 1] return dp[n] ob = Solution() days = [1, 3, 5, 6, 28] print(ob.solve(days))
อินพุต
[1, 3, 5, 6, 28]
ผลลัพธ์
9
