更新次數：0
首列/首欄為字元標頭；表格內為 dp[i][j] 的值；橘色格為本步驟正在更新的格。
很多難題會一再重複算同一小塊，像爬一段很長的樓梯、每階都要重問「到這裡總共幾種走法」，每次從頭數就慢得離譜。動態規劃（Dynamic Programming）的訣竅是把算過的小答案記在一張表格裡，下次遇到直接查、不重算，用一點記憶體換回大量時間。真正難的是怎麼把問題切成合適的「格子」——同一招會因題目不同而長出不同形狀的表格。下面你會看到四種變形：比對兩個字串、幫矩陣排乘法順序、規劃最短環遊路線、以及在樹上挑不相鄰的節點。
延續 DP 的核心思路（重疊子問題 + 最優子結構），以下四個範例展示 DP 狀態設計的不同變形：
dp[i][j]，逐格填表求最少編輯操作數。dp[i][j]，依區間長度由小到大遞推，枚舉分割點求最優括號化。dp[mask][i]（已訪城市集合 + 目前城市），以二進位 mask 表示子集合。dp[u][0/1]（節點 u 選或不選），依後序 DFS 由葉往根遞推。
二維 DP：dp[i][j] 為 s1 前 i 字元轉成 s2 前 j 字元所需的最少操作數（插入/刪除/替換）。
基底 dp[i][0]=i、dp[0][j]=j；字元相同時免費承接對角線，否則取替換/刪除/插入三者最小值 + 1。
區間 DP：dp[i][j] 為矩陣 i..j 相乘的最少乘法次數。依區間長度由小到大遞推，
每個區間枚舉所有分割點 k，取 dp[i][k] + dp[k+1][j] + d[i-1]·d[k]·d[j] 的最小值，
並記錄分割點以重建最優括號化順序。
狀態 dp[mask][i]：已訪城市集合為 mask（二進位表示）、目前在城市 i 的最短距離；
起點固定為城市 0。dp[mask|{j}][j] = min(dp[mask|{j}][j], dp[mask][i] + dist[i][j])。
本節固定使用三組預設距離矩陣（純函式輸入，不做隨機城市，n ≤ 5）。
每個節點 u 有兩態：dp[u][0] 不選 u、dp[u][1] 選 u。
後序 DFS 先算完所有子節點：dp[u][1] = w[u] + Σ dp[child][0]、
dp[u][0] = Σ max(dp[child][0], dp[child][1])。最終答案為
max(dp[root][0], dp[root][1])，並回溯標出被選中的節點集合。