d378: 最小路徑

出處 http://zerojudge.tw/ShowProblem?problemid=d378

內容 ：

現在有一張地圖，凡是走過某一個格子，都會消耗體力，所以請你找出最少消耗體力值。

現在老鼠在地圖的左上角，在走的時候時，所以只能往右或下走，之後要走到右下角，

走過的點上的數字必須加總，請輸出加總的數字最小的。

測資一 :

0 7 8 9

1 5 1 1

2 4 10 0

可以走 0 → 7 → 8 → 9 → 1 → 0 SUM = 7 + 8 +9 + 1 = 25

0 → 1 → 5 → 1 → 1 → 0 SUM = 1 + 5 + 1 + 1 =8

0 → 7 → 8 → 1 → 10 → 0 SUM = 7 + 8 + 1 + 10 = 26

.

.

以此類推，只輸出最小值 8

" 左上角跟右下角必為 0 "

輸入說明 ：

輸入的每第一行會有兩個數字 N, M ( 2 ≦ N , M ≦ 101)

之後會有 N 行，每行上會有 M 個數字 G ( 1 ≦ G ≦ 20 )

輸出說明 ：

對每組地圖先輸出 "Case #%d :"

輸出從左上走到右下最少的體力消耗

範例輸入 ：

3 4

0 7 8 9

1 5 1 1

2 4 10 0

2 2

0 1

1 0

範例輸出 ：

Case #1 :

8

Case #2 :

1

提示 ：

DP

出處 ：

DP (管理：morris1028)

解題策略

使用DP，因為(i,j)只能來自於(i-1,j)與(i,j-1)較小的值，加上原本的值

dp[i][j]=min(dp[i-1][j],dp[i][j-1])+map[i][j];