概念

動態規劃，簡稱 DP，是一種演算法的設計概念。其核心思想是通過解決許多相似性質的小問題，來計算我們所關心的大問題的答案。通常，這些小問題之間存在著遞迴關係，但 DP 的精髓在於，它會將計算過的小問題答案儲存起來，以避免重複計算。這種方法可以減少不必要的計算，通常被描述為一種以空間換取時間的方式。

實作

DP 的實作方式有兩種主要方法：Top-down 和 Bottom-up。Top-down 基本上是在計算答案之前先檢查是否已經計算過。如果已經計算過，則直接返回結果；如果尚未計算，則計算並將結果儲存，以便以後使用。Bottom-up 則是從最小的子問題開始計算，並依次計算更大的問題，通常使用迭代方式完成。

競程應用

動態規劃在競程中是一個常見的出題方向，因為它不像其他演算法一樣有固定的模板，可以適應各種不同的問題。一些經典的 DP 問題包括背包問題、找零錢、最大連續區間和、最長遞增子序列（LIS）、最長公共子序列（LCS）等。因此，要精通 DP 需要不斷練習、閱讀、思考並實際應用，並沒有快速進步的捷徑。

總結

這一篇文章只是簡單簡介一下 DP 的一些概念及實作方式，後面會以題目講解來讓大家更認識動態規劃也可以有實作範例可以解釋，而題目會以經典題型為主，偶爾才會穿插一些不定型的題目