Min Cost Path

1. GeeksforGeeks: Dynamic Programming | Set 6 (Min Cost Path)

假設一個陣列如下:

1 2 3
    4 8 2
    1 5 3

現在我們要從(0,0)到(2,2),求花費少的路徑

行動模式只有:
往右,
往下,
往右下

上面陣列花費最少的路徑為: 1+2+2+3

Memoization (Top Down): 省空間

int min(int a, int b, int c)
{
    if(a < b)
        return a < c ? a:c;
    else
        return b < c ? b:c;
}

int MinCost(int a[R][C], int x, int y)
{
    if(x<0 || y<0)
        return INT_MAX;
    else if (x==0 && y==0)
        return a[x][y];
    else
        return a[x][y] + min(MinCosta(a,x-1,y-1),
                             MinCosta(a,x,y-1),   
                             MinCosta(a,x-1,y));
}

Tabulation (Bottom Up): 較快,不用重複計算

int min(int a, int b, int c)
{
    if(a < b)
        return a < c ? a:c;
    else
        return b < c ? b:c;
}

int MinCost(int a[R][C], int x, int y)
{
    int i, j;
    int tc[R][C];   //temporary array

    tc[0][0] = a[0][0];

    for(i=1; i<=x; i++)
        tc[i][0] = a[i][0]+tc[i-1][0];
    for(j=1; j<=y; j++)
        tc[0][j] = a[0][j]+tc[0][j-1];
    for(i=1; i<=x; i++)
        for(j=1; j<=y; j++)
            tc[i][j] = a[i][j] + min(tc[i-1][j-1],
                                     tc[i][j-1],
                                     tc[i-1][j]);
    return tc[x][y];
}