# 【題解】ZeroJudge d378: 最小路徑

• 老鼠在地圖上走的時候時，只能往右或下走。
• dp[i][j]初始值即輸入測資：老鼠走經(i, j)那一格時消耗的體力。
• Case-I (row-0)：只能從左邊那一格走過來。dp[0][j] = dp[0][j-1] + dp[0][j]
• Case-II (column-0)：只能從上面那一格走下來。dp[i][0] = dp[i-1][0] + dp[i][0]
• Case-III (其它格子)：可經由左邊或上方那一格走過來，選擇消耗體力較小的路徑，dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + dp[i][j]
```#include <iostream>
using namespace std;

int c = 0, n, m, a[1005][1005];

int main() {
while (cin >> n >> m){
c++;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> a[i][j];
}
}
for (int i = 1; i < n; i++){
a[i][0] += a[i-1][0];
}
for (int j = 1; j < m; j++){
a[0][j] += a[0][j-1];
}
for (int i = 1; i < n; i++){
for (int j = 1; j < m; j++){
a[i][j] += min(a[i-1][j], a[i][j-1]);
}
}
cout << "Case #" << c << " :\n" << a[n-1][m-1]<< "\n";
}
}
```

Python code (credit: Amy Chou)

```T = 1
while True:
try:
N, M = map(int, input().split())
dp = []
for i in range(N):
tmp = list(map(int, input().split()))
dp.append(tmp)

for j in range(1, M):
dp[0][j] += dp[0][j-1]

for i in range(1, N):
dp[i][0] += dp[i-1][0]

for i in range(1, N):
for j in range(1, M):
dp[i][j] += min(dp[i-1][j], dp[i][j-1])

print(f"Case #{T} :")
print(dp[N-1][M-1])
T += 1
except:
break
```