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

程式碼 ：

#include<stdio.h>

int main()
{
    int i,j,n,m,count;
    int map[101][101];
    
    count = 1;
    while(scanf("%d%d",&n,&m)==2)
    {
        for(i=0; i<n; i++)
            for(j=0; j<m; j++)
                scanf("%d",&map[i][j]);
        
        for(i=1; i<n; i++)
            map[i][0] += map[i-1][0];
        
        for(j=1; j<m; j++)
            map[0][j] += map[0][j-1];
        
        for(i=1; i<n; i++)
            for(j=1; j<m; j++)
            {
                if(map[i-1][j] > map[i][j-1])
                    map[i][j] += map[i][j-1];
                else
                    map[i][j] += map[i-1][j];
            }
        
        printf("Case #%d :\n%d\n",count++,map[n-1][m-1]);
    }
    
    return 0;
}

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