DP 計數經典：UVA 885 Pascal's Travels & POJ 2704

Pascal's Travels (UVA 885)

n×n 棋盤，每格數字 k 表示必須向右或向下跳 k 格。從 (1,1) 到 (n,n) 的路徑數。n ≤ 34，答案 < 2⁶³。

DP：dp[i][j] 到達 (i,j) 的路徑數。轉移：

if (val[i][j] > 0) {
    if (i+val <= n) dp[i+val][j] += dp[i][j];
    if (j+val <= n) dp[i][j+val] += dp[i][j];
}

按行列順序遍歷即可（拓撲序）。

Walking on the Safe Side (POJ 2704)

W 橫街、N 縱街，部分路口禁行。從 (1,1) 到 (W,N) 最短路徑數（只能右/下）。

DP：dp[i][j] = (blocked? 0 : dp[i-1][j] + dp[i][j-1])。輸入給每條橫街的禁行縱街編號，需解析構建 blocked 矩陣。

共同點

• 網格 DP，狀態轉移只依賴左/上。
• 長整型防溢出。
• 多測試用例處理輸入格式（空行分隔）。