動態規劃的基底情況（base cases）

轉移告訴你如何由較小狀態建出某狀態的答案，但你不能無止境地往下建——到了某處你會抵達最小的狀態，那些沒有更小片段可倚靠的狀態。它們就是基底情況，你必須依問題的意義，親手直接填入它們的答案。它們是整張表所倚靠的地基。地基若錯，建在其上的每個值都會繼承這個錯誤，所以基底情況值得與遞迴本身一樣多的小心。

具體來說，基底情況是你在任何迴圈或遞迴之前就寫好、轉移不准去計算的那些項。對費氏數，它們是 fib(0)=0 與 fib(1)=1。對最長共同子序列，dp[i][0] = 0 且 dp[0][j] = 0，意思是任何字串與空字串的最長共同子序列是空的。對編輯距離，dp[i][0] = i（把長度 i 的字串變成空字串要花 i 次刪除）且 dp[0][j] = j（j 次插入）。對一個計數型動態規劃，基底情況常是 dp[空] = 1——「什麼都不做」恰好有一種方式。每個基底情況都是一個微小實例，其答案你無需任何遞迴就能直接讀出，而把它的值定對（是 0、1、無窮大，還是 i？）是因問題而異的判斷。

基底情況也編碼了可行性的邊界。在一個必須排除不可行情境的最佳化裡，你常以一個哨兵值替不可能的狀態播種——求最小時用正無窮大，求最大時用負無窮大——好讓「取最佳」的運算自動避開它們。經典例子是硬幣找零：dp[0] = 0（零枚硬幣湊出金額 0），而對每個正金額，dp[amount] 起始為無窮大，於是一個湊不出來的金額會維持無窮大，永不被誤認為可達。邊界上的差一錯誤與哨兵值錯誤是最常見的動態規劃臭蟲之一，正因為表的其餘部分看起來正確，卻悄悄建立在一個壞掉的邊上。