動态規劃——787. K 站中轉内最便宜的航班

文章目錄

• 題目描述
• 解答（動态規劃）
• 總結

題目描述

難度middle

有 n 個城市通過 m 個航班連接配接。每個航班都從城市 u 開始，以價格 w 抵達 v。

現在給定所有的城市和航班，以及出發城市 src 和目的地 dst，你的任務是找到從 src 到 dst 最多經過 k 站中轉的最便宜的價格。 如果沒有這樣的路線，則輸出 -1。

解答（動态規劃）

class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        dp = [[float("inf")]*n for _ in range(K+1)]
        for s, d, p in flights:
            if s == src:
                dp[0][d] = p
        for k in range(1, K+1):
            for s, d, p in flights:
                dp[k][d] = min(dp[k-1][d], dp[k-1][s] + p, dp[k][d])
        return dp[-1][dst] if dp[-1][dst] != float("inf") else -1
           

經典的動态規劃題目，建立一個清單記錄從src出發不超過k次中轉到達各地的最小價格，dp大小為(k+1)*n。

首先初始化從src直達各地的價格，然後周遊中轉次數和航班。

狀态轉移方程為dp[k][d] = min(dp[k-1][d], dp[k-1][s] + p, dp[k][d])。

即：

a) k-1次中轉到達d處（傳遞小于k次中轉時的最小價格）

b) k-1次中轉到達s再從s直達d完成k次中轉

c) 之前通過其他路徑k次中轉到達d的最小價格

k次中轉到達d處的最小價格為min(a，b，c)

經過周遊後，dp被指派，dp[k][des]即為所求，若其仍為float(“inf”)則顯然無通往des的路線。

總結

動态規劃題目最關鍵的是，選擇dp數組記錄什麼資料，周遊什麼，狀态轉移方程怎麼建構！