> For the complete documentation index, see [llms.txt](https://851958789.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://851958789.gitbook.io/notes/0787_cheapest_flights_within_k_stops/slt.md).

# Solution1 DP

* 时间复杂度 $O((m+n)k)$

    m 是 flights 长度
* 空间复杂度 $O(n \* k)$

    即 dp 占用的空间

f\[t]\[i] 表示恰好 t 次航班，从 src 到 i 的最下花费。

状态转移方程

f\[t]\[i] = min(f\[t-1]\[j] + cost(j,i)) for every flights 中从 j 到 i 的航班

最多能达的航班数是 k + 1，最后答案为 min(f\[1]\[dst], f\[2]\[dst], ..., f\[k+1]\[dst])

当 t=0 时，f\[0]\[i] 表示不搭航班到 i 的最小花费，有：

* f\[0]\[i] = 0, i == src
* f\[0]\[i] = inf, i != src