# Dynamic Programming[2] - The shortest distance

# (1, 1)에서 (i, j)까지 최소의 셀들의 합으로 가는 방법 (단, 오른쪽이나 아래로만 움직인다.)

∞	∞	∞	∞
∞	5	3	2
∞	4	6	1
∞	1	8	5

1) Recursive 방식

 

#include<stdio.h>
// 순환식 : 중복되는 계산이 많다
int m[4][4] = {
    {999, 999, 999, 999},
    {999, 5, 3, 2},
    {999, 4, 6, 1},
    {999, 1, 8, 5}
};
int mat(int i, int j)
{
    if (i == 1 && j == 1)
    {
        return m[1][1];
    }
    else if (i == 1) {
        return mat(i, j - 1) + m[i][j];
    }
    else if (j == 1) {
        return mat(i - 1, j) + m[i][j];
    }
    else {
        if (mat(i - 1, j) < mat(i, j - 1)) {
            return mat(i - 1, j) + m[i][j];
        }
        else {
            return mat(i, j - 1) + m[i][j];
        }
    }
}
void main() {
    int result = mat(2, 3);
    printf("%d", result);
}

 

2) bottom-up 방식

#include<stdio.h>
// bottom-up 방식
int m[4][4] = {
    {999, 999, 999, 999},
    {999, 5, 3, 2},
    {999, 4, 6, 1},
    {999, 1, 8, 5}
};
 
int L[4][4];
 
void initL()
{
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            L[i][j] = 999;
        }
    }
}
int mat(int n1, int n2)
{
    initL();
    
    for (int i = 1; i <= n1 ; i++)
    {
        for (int j = 1; j <= n2 ; j++)
        {
            if (i == 1 && j == 1)
            {
                L[1][1] = m[1][1];
            }
            else {
                if (L[i][j - 1] < L[i - 1][j])
                {
                    L[i][j] = L[i][j - 1] + m[i][j];
                }
                else
                {
                    L[i][j] = L[i - 1][j] + m[i][j];
                }
            }
        }
    }
    return L[n1][n2];
}
void main() {
    int result = mat(2, 3);
    printf("%d", result);
}